TAILIEUCHUNG - Lecture Theory of automata - Lecture 36

After studying this chapter you will be able to understand: Chomsky Normal Form, Theorem regarding CNF, examples of converting CFG to be in CNF, 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

• Kỹ thuật lập trình
• Theory of automata
• Lecture Theory of automata
• Computer theory
• Theory of computation
• Solution of the Task
• Theorem regarding CNF
• Automata theory
• Automata theory languages
• Automata theory computation
• Pushdown automata
• Context Free grammars
• Regular languages
• Additional classes
• Intractable problems
• Properties of context free languages
• Polish notation
• Total language tree
• Null production
• Nullable production
• The START state
• Nondeterministic PDA
• Equivalent PDA
• PDA corresponding to CFG
• STACK alphabet
• Computer science
• CFG corresponding
• Conversion form of PDA
• Recap of PDA
• Non context free language
• Parsing techniques
• Turing machine
• DELETE subprogram
• Kleene’s theorem
• NFA corresponding
• Concatenation of FAs
• Distinguishable strings
• Indistinguishable strings
• Recap theorem
• Moore machine
• Mealy machine
• Applications of complementing
• Equivalent machines
• Mealy machines
• Complement of a language
• Non regular language
• Example of nonregular language
• Pumping lemma version I