1. Lecture # 32 Theory Of Automata By Dr. MM Alam 1
2. Lecture 31 at a glance.. • Non Context Free Languages • How to determine Non Context Free languages • Pumping Lemma for Non Context Free Languages • JFLAP For Pumping Lemma for Non Context Free Languages 2
3. • JFLAP for Context Free Pumping Lemma Repeat
4. Decidability In this chapter, we will focus on three problems 1. Whether or not the given CFG generates any word? Problem of emptiness of CFL. 2. To determine whether the nonterminal X is ever used in the derivation of word from the given CFG? Problem of usefulness. 3. Whether or not the given CFG generates the finite language? Problem of finiteness. 4
5. Whether or not the given CFG generates any word? Problem of emptiness of CFL. Consider the following Example: SAB, A BSB, BCC CSS Aa|b C b|bb 5
6. SaB SAB, A BSB, BCC CSS Aa|b ABSB C b|bb Abb BaaS Bbb CSS Bbb and Abb, it can be written as: 6
7. Sabb AbbSbb BaaS CSS Since Sabb has been obtained so, abb is a word in the corresponding CFL. 7
8. To determine whether the nonterminal X is ever used in the derivation of word from the given CFG? Problem of usefulness. Consider the following CFG SAba | bAZ | b AXb | bZa BbAA XaZa|aaa ZZAbA 8
9. To determine whether X is ever used to generate some words, unproductive nonterminals are SAba | bAZ | b determined. Z is AXb | bZa BbAA unproductive nonterminal, XaZa|aaa so eliminating the ZZAbA productions involving Z. SAba|b AXb BbAA Xaaa 9
10. X points to non terminal, so A also. Thus B and S also point to non terminal. So only useful productions shall be used. 10
11. Whether or not the given CFG generates the finite language? Problem of finiteness. Example: Consider the CFG SABa|bAZ|b AXb|bZa BbAA XaZa|bA|aaa ZZAbA Here the nonterminal Z is useless, so by eliminating we get the following grammar: 11
12. SABa|b AXb BbAA XbA|aaa Starting with nonterminal X. It is self- embedded, therefore, the grammar creates an infinite language. SABa|b 12
13. Example: Consider the following CFG in CNF SAA AAA Aa Let x=aaa. To determine whether x can be generated from the given CFG let x=x1x2x3 where x1 = x2=x3 =a 13
14. According to CYK algorithm, the list of nonterminals producing single letter double letter substrings of x and the string x itself, can be determined as follows 14
15. Substring All producing nonterminals x1=a A x2=a A x3=a A x1 x2 S,A x2 x3 S,A x= x1 x2 x3 S,A 15
16. Since S is in the list of producing nonterminals, so aaa can be generated by the given CFG. 16
17. Turing machine Components A Turing machine (TM) consists of the following 1. An alphabet Σ of input letters. 2. An input TAPE is partitioned into cells 3. Having infinite many locations in one direction. 4. initially tape is filled with blanks ( ?’ s). 17
18. Turing machine continued … Input TAPE Cell i Cell ii Cell iii Cell iv a b a ? ... TAPE Head 3. A tape Head can read and replace the character at any cell and afterwards, reposition itself to the left or to the right. 18
19. Turing machine continued … 5. Finite set of states -- exactly one START state and some (may be none) HALT states. Halt is similar to Accept. 6. A Function which is the set of rules, which show that which state is to be entered when a letter is read form the TAPE and what character is to be printed. This function has the format: (letter, letter, direction) 19
20. Example Consider the following Turing machine (a,a,R) (b,b,R) (a,a,R) (b,b,R) ( ?,  ?,R) 1 START 2 3 4 HALT (b,b,R) Let the input string aba be run over this TM 20