Đang chuẩn bị liên kết để tải về tài liệu:
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 note Theory of automata - Lecture 20 Lecture 29 Theory Of Automata By Dr. MM Alam 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 SIS 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 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 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 Pushdown Automata Example Trace the acceptance of 4 4 4 continued POP S 4 READ3 S 4 POP Δ 4 READ1 Δ Δ POP Δ Δ READ4 Δ Δ ACCEPT Δ Δ 7 Theorem Statement Given a language L generated by a particular CFG there is a PDA that accepts exactly L. 8 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 PDA Conversion to CFG The word aab can be generated by most derivation in this grammar as follows Working-String Generation Production Used S gt AB S AB Step I gt CCB A CC Step 2 gt aCB C a Step 3 gt aaB C a Step 4 gt aab B b Step 5 10 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 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 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 .