Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Theory of Automata: Lesson 38

Lecture Theory of Automata: Lesson 38. The main topics covered in this chapter include: example of PDA with table for running a string, equivalent PDA, PDA for EVEN-EVEN language; non-derterministic PDA, example of non-derterministic PDA, definition of PUSH DOWN automata, example of non-derterministic PDA, . | 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 START a PUSH a READ1 b b a POP2 POP1 READ2 b a b a REJECT ACCEPT REJECT Note The process of running the string aaabbb can also be expressed in the following table STATE STACK TAPE START aaabbb READ1 aaabbb PUSH a a aaabbb READ1 a aaabbb PUSH a aa aaabbb READ1 aa aaabbb PUSH a aaa aaabbb READ1 aaa aaabbb POP1 aa aaabbb Example contd. STATE STACK TAPE READ2 aa aaabbb POP1 a aaabbb READ2 a aaabbb POP1 aaabbb READ2 aaabbb POP2 aaabbb ACCEPT aaabbb 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 START a PUSH X READ1 b b X X POP2 POP1 READ2 a REJECT ACCEPT Following is an example of PDA corresponding to an FA Example Consider the following FA corresponding to the EVEN EVEN language a a b b b b a a The corresponding PDA will be Example continued ACCEPT REJECT a START READ1 READ2 a b b b a b READ4 READ3 a 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 otherwise rejected. Following is an example of nondeterministic PDA START a POP1 a a b a PUSH a READ1 b b READ2 POP2 PUSH b b POP3 ACCEPT Nondeterministic PDA .