1. Lecture # 31 Theory Of Automata By Dr. MM Alam 1
2. Lecture 30 at a glance… • Using JFLAP for PDA • PDA Conversion to CFG • Chomsky Normal Form Conversion in JFLAP 2
3. What are Non-Context-Free languages • All languages are not CFL. • Languages which are not Context-Free, are called Non-CFL. • This chapter is about proving that all languages are not Context-Free • We will also use the Pumping Lemma with and without JFLAP for the proof of the aforementioned fact. 3
4. Live Production VS Dead Production Definition • A production of the form nonterminal  string of two nonterminals is called a live production. • A production of the form nonterminal  terminal is called a dead production. 4
5. Live Productions Example Thanks to Daniel I Cohen. The above excerpts have been taken from his Book: Automata Theory, Chapter Non Context Free Languages. 5
6. • Finite many words can be generated if a CFG is in CNF and if there is restriction to use the live production at most once each. • It may be noted that every time a live production is applied during the derivation of a word it increases the number of non- terminals by one, similarly, dead productions are applied, it decreases the number of non-terminals by one. 6
7. Self Embedded Nonterminal A nonterminal is said to be self-embedded, if in a given derivation of a word, it ever occurs as a tree descendant of itself 7
8. Theorem (33) Statement: If a CFG is in CNF with p live and q dead productions and if w is a word generated by the CFG, having more than 2p letters then any derivation tree for w has a nonterminal z which is used twice, where the second z is the descended from the first z. 8
9. The nonterminal X is self- embedded 9
10. Example Grammar: S  AX X  SA S  BY Y  SB S  a S  b S  AA S  BB A  a B  b 10
11. S S→AX AX X→SA ASA S→AX AAXA X→SA AASAA S→AX AAAXAA X→SA AAASAAA A→a aAASAAA A→a aaASAAA A→a aaaSAAA S→b aaabAAA A→a aaabaAA A→a aaabaaA A→a aaabaaa 11
12. Consider the following CFG in CNF and the derivation tree of the word bbabbb S  AB A  BC C  AB A  a B  b 12
13. S  AB A  BC C  AB A  a B  b 13
14. S • Non-terminal A is self embedded A B • Look at the triangle – upper one and B C b lower one identified b A B in the lower. • Guess what – B C b Pumping Lemma for CFG in CNF? b A B a 14 b
15. Pumping lemma for CFL in CNF If G is any CFG in CNF with p live productions, then every word w of length more than 2p , then we can break substrings as w=uvxyz, where x is not null string and v and y are both not null string. Thus, all the words of the form uv nxynz, n=1,2,3,… can also be generated by G. 15
16. Pumping Lemma Example Consider the following CFG in CNF: S  PQ Q QS|b P a we derive the word abab as follows: 16
17. Pumping Lemma for CFG Example • w=uvxyz where u=a, v= ʎ, x=b, S y=ab, z= ʎ • Left most is u, P Q within the triangle, the left most is x Q S a and remaining part u is y, since the v Q b P part can also be x null. a b 17 y
18. S • uvvxyyz=a ʎ ʎ babab ʎ =ababab belongs to the P S language generated by the given CFG. a Q S • uvnxynz, n=1,2,3,… belong u to the language generated Q S P Q by the given CFG. b P Q x a b a b y y 18
19. Example • Consider the language L={anbncn :n=1,2,3,…}, let the language L be Context Free language • Let the word w=a200b200c200 of length more than 2p, where p is the number of live productions of its CFG in CNF. • Please follow the observations given on the next slide: 19
20. Observations: Substrings u,v,x,y and z. uv2xy2z can’t belong to L, as all the words in anbncn have: Think on a3b3c3 Only one substring ab Only one substring bc It may be noted that the pumping lemma is satisfied by all CFLs and the languages No substring ac which don’t hold this pumping lemma, can’t be Context Free languages. Such languages are non-CFLs. Following are the No substring ba examples of non-CFL. No substring ca No substring cb For any n=1,2,3,… 20