tailieunhanh - Lecture Theory of automata - Lecture 41

This chapter presents the following content: Recap of PDA in conversion form, example of PDA in conversion form, joints of the machine, new pictorial representation of PDA in conversion form, summary table, row sequence, row language. | Recap lecture 40 Recap of example of PDA corresponding to CFG, CFG corresponding to PDA. Theorem, HERE state, Definition of Conversion form, different situations of PDA to be converted into conversion form Conversion form of PDA Definition: A PDA is in conversion form if it fulfills the following conditions: There is only one ACCEPT state. There are no REJECT states. 3. Every READ or HERE is followed immediately by a POP . every edge leading out of any READ or HERE state goes directly into a POP state. CFG corresponding to PDA No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are any intervening PUSH states (. the POP states must be separated by READs or HEREs). All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every edge has only one label. CFG corresponding to PDA Even before we get to START, a “bottom of STACK” symbol $ is placed on the STACK. If this symbol is | Recap lecture 40 Recap of example of PDA corresponding to CFG, CFG corresponding to PDA. Theorem, HERE state, Definition of Conversion form, different situations of PDA to be converted into conversion form Conversion form of PDA Definition: A PDA is in conversion form if it fulfills the following conditions: There is only one ACCEPT state. There are no REJECT states. 3. Every READ or HERE is followed immediately by a POP . every edge leading out of any READ or HERE state goes directly into a POP state. CFG corresponding to PDA No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are any intervening PUSH states (. the POP states must be separated by READs or HEREs). All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every edge has only one label. CFG corresponding to PDA Even before we get to START, a “bottom of STACK” symbol $ is placed on the STACK. If this symbol is ever popped in the processing it must be replaced immediately. The STACK is never popped beneath this symbol. Right before entering ACCEPT this symbol is popped out and left. CFG corresponding to PDA 7. The PDA must begin with the sequence The entire input string must be read before the machine can accept the word. START PUSH $ HERE POP $ Example Consider the following PDA accepting the language {a2nbn : n = 1,2,3, } Which may be converted to ST POP1 POP2 a RD2 POP3 $ AT RD1 b b a PUSH a a ST PUSH $ POP4 $ POP1 HERE a POP2 POP3 $ AT RD1 POP5 b RD2 a b POP6 a PUSH a PUSH a PUSH $ PUSH a a $ a The above PDA accepts exactly the same language Note It may be noted that any PDA which is conversion form can be considered to be the collection of path segments, where each path segment is of the following form Any string onto the STACK Exactly one STACK character ONE or no input letter READ or HERE or AT START or READ or HERE PUSH POP READ TO FROM Note continued START,