tailieunhanh - Lecture note Theory of automata - Lecture 20

Lecture Theory of automata - Lecture 20 includes the following content: recap theorem, example, finite automaton with output, moore machine, examples. | Lecture # 29 Theory Of Automata By Dr. MM Alam 1 1 Lecture 28 at a Glance Push Down Automata Definition PDA Symbols Deterministic PDA Examples Non-Deterministic PDA Examples 2 Pushdown Automata Example Consider the language generated by the CFG: S → S + S I S * S | 4 The terminals are +, *, and 4 and the only nonterminal is S. 3 Pushdown Automata The following PDA accepts this language: 4 Pushdown Automata Example Trace the acceptance of 4 + 4 * 4 5 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 Pushdown Automata Example Trace the acceptance of 4 + 4 * 4 (continued) 6 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 Pushdown Automata Example Trace the acceptance of 4 + 4 * 4 (continued) 7 POP S * 4 READ3 S 4 POP Δ 4 READ1 Δ Δ POP Δ Δ READ4 Δ Δ ACCEPT Δ Δ Theorem Statement: Given a language | Lecture # 29 Theory Of Automata By Dr. MM Alam 1 1 Lecture 28 at a Glance Push Down Automata Definition PDA Symbols Deterministic PDA Examples Non-Deterministic PDA Examples 2 Pushdown Automata Example Consider the language generated by the CFG: S → S + S I S * S | 4 The terminals are +, *, and 4 and the only nonterminal is S. 3 Pushdown Automata The following PDA accepts this language: 4 Pushdown Automata Example Trace the acceptance of 4 + 4 * 4 5 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 Pushdown Automata Example Trace the acceptance of 4 + 4 * 4 (continued) 6 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 Pushdown Automata Example Trace the acceptance of 4 + 4 * 4 (continued) 7 POP S * 4 READ3 S 4 POP Δ 4 READ1 Δ Δ POP Δ Δ READ4 Δ Δ ACCEPT Δ Δ Theorem Statement: Given a language L generated by a particular CFG, there is a PDA that accepts exactly L. 8 ∆ 8 9 The nondeterministic PDA. 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 B → b C → a. PDA Conversion to CFG 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 ∆ 10 We start with Immediately we push the symbol S onto the STACK. We pop the S and then we PUSH B, PUSH 11 STACK TAPE ∆ aab STACK TAPE S aab STACK TAPE AB aab PDA Conversion to CFG ∆ 11 PDA Conversion to CFG We again feed back into the central POP. The production we must now simulate is a A → CC. This is done by popping the A and following the path PUSH C, PUSH C. Again we feed back into the central POP. This time we must simulate the reduction C → a. POP C and then read the