FIT2014 Lecture Notes - Lecture 13: Binary Tree, Parse Tree, Longest Path Problem
28 Jun 2018
School
Department
Course
Professor
Lecture 13 : Chomsky Normal Forum
CNF is a special type of context free grammar
Nonterminal Nonterminal Nonterminal (live production)
Or Nonterminal terminal (dead production)
For any context free language L, the on empty words in L can be generated by a grammar in CNF
Proof:
1. First eliminate all 𝜀 production as it doesn’t satisfy the requirement
a. May need some new production to keep the effect on an empty production
2. For each terminal a, ensure that there is a production of the form A a and replace a in all other
production by A
3. Elimate all unit production
4. For any production that has more than 2 nonterminals on the right-hand side, split them into a
sequence of productions that have only 2 nonterminals on the right-hand side.
This gives us a Cocke YOunfer Kasami (CYK( algorithm
- For each CFG and string s, we can decide whether or not s is generated by CFg
- Bottom up prsing
Also pumping lemma for Context free gramma which used to show there exists non context free language
CYK algorithm:
Proof: find the CNF for non empty words generate by grammae
- Add S 𝜀 if 𝜀 can be generated by CFG
- If s = 𝜀 then state that s can be generate if and onlyof S 𝜀 is a production
Document Summary
Cnf is a special type of context free grammar. For any context free language l, the on empty words in l can be generated by a grammar in cnf. This gives us a cocke younfer kasami (cyk( algorithm. For each cfg and string s, we can decide whether or not s is generated by cfg. Also pumping lemma for context free gramma which used to show there exists non context free language. Proof: find the cnf for non empty words generate by grammae. Add s if can be generated by cfg. If s = then state that s can be generate if and onlyof s is a production. Assume s = t1 t2 tn is non-empty. For each letter tk find the non-terminals which can produce tk. For each of the following pairs: t1 t2, t2 t3, , tn-1 tn find the non-terminals that can produce the pair.
