Lecture 12 (Converting PDAs to CFGs), 10/9/17

Concepts, definitions (in italics):

o    Converting a regular PDA to a simple PDA

o    Involves three steps, that must be done in order (to avoid undoing a condition)

o    Note that if we start and end with empty stack, first transition always pushes and last one always pops

         For every simple PDA, there is an equivalent CFG

         Proof involves an algorithm for converting a simple PDA to a CFG

o    All non-terminals are of the form Vp,q

o    Vp,q corresponds to the set of strings that can be accepted as we go from state p to q, starting and ending with empty stack

o    Vq-inital,q-final is the start variable

o    Three types of rules created

         The set of languages accepted by PDAs is the same as generated by CFGs

  Because there is an algorithm that, given a CFG G, will create an equivalent PDA MG.

  The proof that L(G) = L(MG) has two parts (if w is in L(G), it is accepted by MG, and vice versa) both done by induction.

  Because there is an algorithm that, given a simple PDA M, will create an equivalent CFG GM.

  The proof that L(M) = L(GM) has two parts (if w is accepted by M there is a derivation for it in GM, and vice versa), both done by induction.

         Closure rules for CFLs:

o    Concatenation, union, star

         CFLs are not closed under intersection or complement

         Proving that CFLs are not closed under intersection:

Reading:

Skills:

         Understand the role that recursion plays in proving that for every valid computation of simple PDA, there is an equivalent valid parse tree of the CFG