Lecture Theory of Automata: Lesson 40. The main topics covered in this chapter include: 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, . | Recap lecture 39 PDA corresponding to CFG Examples of PDA corresponding to CFG 1 Example Consider the following CFG S XY X aX bX a Y Ya Yb a First of all converting the CFG to be in CNF introduce the nonterminals A and B as A a B b The following CFG is in CNF 2 Example continued S XY X AX BX a Y YA YB a A a B b The PDA corresponding to the above CFG will be 3 a a a b RD1 RD3 RD4 RD2 B ST A AT X Y PH S PP RD5 S X X Y Y PH Y PH X PH X PH A PH B PH X PH A PH B PH Y PH Y Theorem Given a PDA that accepts the language L there exists a CFG that generates exactly L. Before the CFG corresponding to the given PDA is determined the PDA is converted into the standard form which is called the conversion form. Before the PDA is converted into conversion form a new state HERE is defined which is placed in the middle of any edge. 5 CFG corresponding to PDA continued Like READ and POP states HERE states are also numbered . RD7 a RD9 b becomes RD7 a HERE3 RD9 b 6 Conversion form of PDA Definition A PDA is in conversion form if it fulfills the following conditions 1. There is only one ACCEPT state. 2. 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. 7 CFG corresponding to PDA 4. 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 . 5. All branching deterministic or nondeterministic occurs at READ or HERE states none at POP states and every edge has only one label. 8 CFG corresponding to PDA 6. 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. 9 CFG corresponding to PDA 7. The PDA must begin with the sequence .
