tailieunhanh - 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 . | 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 PUSH X REJECT ACCEPT START READ1 X READ2 a b POP2 ∆ POP1 ∆ b ∆ ∆ a X Following is an example of PDA corresponding to an FA Example Consider the following FA corresponding to the EVEN-EVEN language The corresponding PDA will be a a a a b b b b Example continued a a a a b b b b READ4 READ1 READ2 READ3 START ACCEPT REJECT REJECT REJECT Nondeterministic PDA Like TGs and NFAs, if in a PDA there are more than one outgoing edges at READ or POP states with one label, then it creates nondeterminism and the PDA is called nondeterministic PDA. In nondeterministic PDA no edge is labeled by string of terminals or nonterminals, like that can be observed in TGs. Also if there is no edge for any letter to be read from the TAPE, the machine crashes and the string is rejected. Nondeterministic PDA continued In nondeterministic PDA a string may trace more than one paths. If there exists at least one path traced by a string leading to ACCEPT state, then the string is supposed to be accepted,