TAILIEUCHUNG - Lecture Theory of automata - Lecture 38
The main contents of this chapter include all of the following: Example of PDA with table for running a string, Equivalent PDA, PDA for EVEN EVEN Language. Non-Derterministic PDA, Example of Non-Derterministic PDA (for EVEN PALINDROME), Definition of PUSH DOWN Automata, with table for running running the string 4+4*4, Note for choice of paths at POP state keeping in view left most derivation,. | Recap lecture 37 New format for FAs, input TAPE, START, ACCEPT , REJECT, READ states Examples of New Format of FAs, PUSHDOWN STACK , PUSH and POP states, Example of PDA PUSH a START REJECT REJECT ACCEPT READ1 a READ2 a b POP2 b, ∆ ∆ POP1 ∆ b ∆ a a,b aaabbb∆ aa∆ POP1 aaabbb∆ aaa∆ READ1 aaabbb∆ aaa∆ PUSH a aaabbb∆ aa∆ READ1 aaabbb∆ aa∆ PUSH a aaabbb∆ a∆ READ1 aaabbb∆ a∆ PUSH a aaabbb∆ ∆ READ1 aaabbb∆ ∆ START TAPE STACK STATE Note: The process of running the string aaabbb can also be expressed in the following table aaabbb∆ ∆ POP2 aaabbb∆ ∆ ACCEPT aaabbb∆ ∆ READ2 aaabbb∆ ∆ aaabbb∆ a∆ aaabbb∆ a∆ aaabbb∆ aa∆ READ2 POP1 READ2 POP1 TAPE STACK STATE Example contd. It may be observed that the above PDA accepts the language {anbn : n=0,1,2,3, }. Note It may be noted that the TAPE alphabet Σ and STACK alphabet , may be different in general and hence the PDA equivalent to that accepting {anbn: n=0,1,2,3 } discussed above may be .
đang nạp các trang xem trước
