tailieunhanh - Lecture Theory of Automata: Lesson 36

Lecture Theory of Automata: Lesson 36. The main topics covered in this chapter include: chomsky normal form, theorem regarding CNF, examples of converting CFG to be in CNF, productions of the form nonterminal, example of an FA corresponding to regular CFG, left most and right most, . | Recap lecture 35 Regular grammar null productions and examples nullable productions and examples unit productions and example Chomsky Normal Form Definition Chomsky Normal Form Chomsky Normal Form CNF If a CFG has only productions of the form nonterminal string of two nonterminals or nonterminal one terminal then the CFG is said to be in Chomsky Normal Form CNF . Note It is to be noted that any CFG can be converted to be in CNF if the null productions and unit productions are removed. Also if a CFG contains nullable productions as well then the corresponding new production are also to be added. Which leads the following theorem Theorem All NONNULL words of the CFL can be generated by the corresponding CFG which is in CNF . the grammar in CNF will generate the same language except the null string. Following is an example showing that a CFG in CNF generates all nonnull words of corresponding CFL. Example Consider the following CFG S aSa bSb a b aa bb To convert the above CFG to be in CNF introduce the new productions as A a B b then the new CFG will be S ASA BSB AA BB a b A a B b Example continued Introduce nonterminals R1 and R2 so that S AR1 BR2 AA BB a b R1 SA R2 SB A a B b which is in CNF. It may be observed that the above CFG which is in CNF generates the NONNULLPALINDROME which does not contain the null string. Example Consider the following CFG S ABAB A a B b Here S ABAB is nullable production and A B are null productions. Removing the null productions A and B and introducing the new productions as S BAB AAB ABB ABA AA AB BA BB A B Example continued Now S A B are unit productions to be eliminated as shown below S A gives S a using A a S B gives S b using B b Thus the new resultant CFG takes the form S BAB AAB ABB ABA AA AB BA BB a b A a B b Introduce the nonterminal C where C AB so that Example continued S BAB AAB ABB ABA AA AB BA BB a b A a B b C AB S CC BC AC CB CA AA C BA BB a b is the CFG in CNF. Task Convert the following CFG to be in CNF S ABAB A a B