1. Lecture # 29 Theory Of Automata By Dr. MM Alam 1
2. Lecture 28 at a Glance… • Push Down Automata Definition • PDA Symbols • Deterministic PDA Examples • Non-Deterministic PDA Examples 2
3. Pushdown Automata • Example • Consider the language generated by the CFG: S→ S+SIS *S|4 • The terminals are +, *, and 4 and the only nonterminal is S. 3
4. Pushdown Automata • The following PDA accepts this language: 4
5. Pushdown Automata • Example • Trace the acceptance of 4 + 4 * 4 STATE STACK TAPE START Δ 4 +4 * 4 PUSH1 S S 4 +4 * 4 POP Δ 4 +4 * 4 PUSH2 S S 4 +4 * 4 PUSH3 + +S 4 +4 * 4 PUSH4 S S+S 4 +4 * 4 5
6. Pushdown Automata • Example • Trace the acceptance of 4 + 4 * 4 (continued) STATE STACK TAPE POP +S 4 +4 * 4 READ1 +S 4*4 POP S 4*4 READ2 S 4*4 POP Δ 4*4 PUSH5 S S 4*4 PUSH6 * *S 4*4 PUSH7 S S*S 4*4 POP *S 4*4 READ1 *S *4 6
7. Pushdown Automata • Example • Trace the acceptance of 4 + 4 * 4 (continued) POP S *4 READ3 S 4 POP Δ 4 READ1 Δ Δ POP Δ Δ READ4 Δ Δ ACCEPT Δ Δ 7
8. Theorem Statement: Given a language L generated by a particular CFG, there is a PDA that accepts exactly L. 8
9. PDA Conversion to CFG STACK alphabet : Γ = {S, A, B, C} TAPE alphabet: S = {a, b} Let us consider the following CFG in CNF S → SB S → AB A → CC The nondeterministic B→b PDA. C → a. 9
10. PDA Conversion to CFG • The word aab can be generated by most derivation in this grammar as follows: Working-String Generation Production Used S => AB S → AB Step I =>CCB A → CC Step 2 =>aCB C→a Step 3 =>aaB C→a Step 4 => aab B→b Step 5 10
11. PDA Conversion to CFG • We start with STACK TAPE ∆ aab • Immediately we push the symbol S onto the STACK. STACK TAPE S aab STACK TAPE • AB then we PUSH We pop the S and aab B, PUSH 11
12. PDA Conversion to CFG • We again feed back into the central POP. The production we must now simulate is a A → CC. This is STACK TAPE done by popping the CCB aab A and following the path PUSH C, PUSH C. STACK TAPE CB aab 12
13. PDA Conversion to CFG • We again feed back into the central POP. The production we must now simulate is a STACK TAPE A → CC. This is CCB aab done by popping the A and following the path PUSH C, PUSH C. STACK TAPE CB aab 13
14. PDA Conversion to CFG • The next production we must simulate is another C  a. Again we POP C and READ a. STACK TAPE B aab • This time when we STACK TAPE enter the central ∆ aab POP we simulate the last production in the 14
15. PDA Conversion to CFG • We now reenter the POP, and we must make sure that both STACK and TAPE are empty. POP ∆ → READ3 → ACCEPT • To accept a word we must follow its left- most derivation from the CFG. If the 15
16. PDA Conversion to CFG • Then at this point in the corresponding PDA-processing the status of the STACK and TAPE should be STACK TAPE ZWV ababbbaab STACK TAPE ∆ ababbbaab • This process continues until we have derived the 16
17. PDA Conversion to CFG • Example S → AB B → AB B→a A → BB A→a B→b 17
18. Left- State STACK TAPE most derivatio n START ∆ baaab S PUSH S S baaab POP ∆ baaab PUSH B B baaab => AB PUSHA AB baaab POP B baaab PUSH B BB baaab ⇒ BBB PUSH B BBB baaab POP BB baaab =>bBB READ3 BB baaab POP B baaab PUSH B BB baaab 18
19. Babb READ3 BB baaab POP B baaab PUSH B BB baaab BaBB Push A ABB baaab POP BB baaab BaBB READ1 B baaab POP B baaab ⇒ bAAB READ2 B baaab POP ∆ baaab PUSH B B baaab baaAB PUSH A AB baaab Pop B baaab 19
20. baaAB READ1 B baaab POP ∆ baaab baaab READ3 ∆ baaab POP ∆ baaab READ4 ∆ baaab ACCEPT ∆ baaab 20