Slide 1Normal FormsSlide 3Normal Forms for GrammarsSlide 5Normal Forms ExistConverting to a Normal FormRule SubstitutionSlide 9Slide 10Slide 11Conversion to Chomsky Normal FormSlide 13Removing -ProductionsUnit ProductionsSlide 16Slide 17Slide 18Mixed RulesSlide 20Long RulesAn ExampleSlide 23Slide 24Slide 25The Price of Normal FormsContext-Free GrammarsNormal FormsChapter 11Normal FormsA normal form F for a set C of data objects is a form, i.e., a set of syntactically valid objects, with the following two properties: ● For every element c of C, except possibly a finite set of special cases, there exists some element f of F such that f is equivalent to c with respect to some set of tasks.● F is simpler than the original form in which the elements of C are written. By “simpler” we mean that at least some tasks are easier to perform on elements of F than they would be on elements of C.Normal FormsIf you want to design algorithms, it is often useful to have a limited number of input forms that you have to deal with.Normal forms are designed to do just that. Various ones have been developed for various purposes. Examples:● Clause form for logical expressions to be used in resolution theorem proving● Disjunctive normal form for database queries so that they can be entered in a query by example grid.● Various normal forms for grammars to support specific parsing techniques.Normal Forms for GrammarsChomsky Normal Form, in which all rules are of one of the following two forms: ● X  a, where a  , or● X  BC, where B and C are elements of V - .Advantages:● Parsers can use binary trees.● Exact length of derivations is known: SA BA A B B a a b B B b bNormal Forms for GrammarsGreibach Normal Form, in which all rules are of the following form:● X  a  , where a   and   (V - )*. Advantages: ● Every derivation of a string s contains |s| rule applications. ● Greibach normal form grammars can easily be converted to pushdown automata with no - transitions. This is useful because such PDAs are guaranteed to halt.Normal Forms ExistTheorem: Given a CFG G, there exists an equivalent Chomsky normal form grammar GC such that: L(GC) = L(G) – {}.Proof: The proof is by construction. Theorem: Given a CFG G, there exists an equivalent Greibach normal form grammar GG such that: L(GG) = L(G) – {}.Proof: The proof is also by construction.Converting to a Normal Form1. Apply some transformation to G to get rid of undesirable property 1. Show that the language generated by G is unchanged.2. Apply another transformation to G to get rid of undesirable property 2. Show that the language generated by G is unchanged and that undesirable property 1 has not been reintroduced.3. Continue until the grammar is in the desired form.Rule SubstitutionX  aYcY  bY  ZZWe can replace the X rule with the rules:X  abcX  aZZcX  aYc  aZZcRule SubstitutionTheorem: Let G contain the rules: X  Y and Y  1 | 2 | … | n , Replace X  Y by: X  1, X  2, …, X  n. The new grammar G will be equivalent to G.Rule SubstitutionTheorem: Let G contain the rules: X  Y and Y  1 | 2 | … | n Replace X  Y by: X  1, X  2, …, X  n. The new grammar G will be equivalent to G.Rule SubstitutionReplace X  Y by: X  1, X  2, …, X  n. Proof: ● Every string in L(G) is also in L(G):If X  Y is not used, then use same derivation.If it is used, then one derivation is:S  …  X  Y  k  …  wUse this one instead:S  …  X  k  …  w● Every string in L(G) is also in L(G): Every new rule can be simulated by old rules.Conversion to Chomsky Normal Form1. Remove all -rules, using the algorithm removeEps.2. Remove all unit productions (rules of the form A  B). 3. Remove all rules whose right hand sides have length greater than 1 and include a terminal: (e.g., A  aB or A  BaC) 4. Remove all rules whose right hand sides have length greater than 2:(e.g., A  BCDE)Remove all  productions: (1) If there is a rule P  Q and Q is nullable, Then: Add the rule P  . (2) Delete all rules Q  .Removing -ProductionsExample:S  aAA B | CDCB  B  aC  BDD  bD  Removing -ProductionsUnit ProductionsA unit production is a rule whose right-hand side consists of a single nonterminal symbol. Example:S  X YX  AA  B | aB  bY  TT  Y | cremoveUnits(G) = 1. Let G = G. 2. Until no unit productions remain in G do: 2.1 Choose some unit production X  Y. 2.2 Remove it from G. 2.3 Consider only rules that still remain. For every rule Y  , where   V*, do: Add to G the rule X   unless it is a rulethat has already been removed once. 3. Return G.After removing epsilon productions and unit productions, all rules whose right hand sides have length 1 are in Chomsky Normal Form.Removing Unit ProductionsremoveUnits(G) = 1. Let G = G. 2. Until no unit productions remain in G do: 2.1 Choose some unit production X  Y. 2.2 Remove it from G. 2.3 Consider only rules that still remain. For every rule Y  , where   V*, do: Add to G the rule X   unless it is a rule that hasalready been removed once. 3. Return G.Removing Unit ProductionsExample: S  X YX  AA  B | aB  bY  TT  Y | cremoveUnits(G) = 1. Let G = G. 2. Until no unit productions remain in G do: 2.1 Choose some unit production X  Y. 2.2 Remove it from G. 2.3 Consider only rules that still remain. For every rule Y  , where   V*, do: Add to G the rule X   unless it is a rule that hasalready been removed once. 3. Return G.Removing Unit ProductionsExample: S  X YX  AA  B | aB  bY  TT  Y | cS  X YA  a | bB  bT  cX  a | bY  cMixed Rules removeMixed(G) = 1. Let G = G. 2. Create a new nonterminal Ta for each terminal a in . 3. Modify each rule whose right-hand side has length greater than 1 and that contains a terminal symbol by substituting Ta for each