NPDA to CFG/CFL

 Given a NPDA  M = ( Q, Sigma, Gamma, delta, q0, Z0, Phi) and
  Sigma intersection Gamma = Phi,
  Construct a CFG  G = ( V, T, P, S )

  Set T = Sigma
      S = S
      V = { S } union { [q,A,p] | q and p in Q and A in Gamma }
          This can be a big set! q is every state with A every Gamma with
          p every state. The cardinality of V, |V|=|Q|x|Gamma|x|Q|
          Note that the symbology [q,A,p] is just a variable name.
          (the states in the NPDA are renamed q0, q1, ... if necessary)

  Construct the productions in two stages, the S -> , then the [q,A,p] ->

  S -> [q0,Z0,qi]  for every qi in Q (including q0)  |Q| of these productions

  [qi,A,qm+1] -> a[qj,B1,q2][q2,B2,q3][q3,B3,q4]...[qm,Bm,qm+1] is created
  for each q2, q3, q4, ..., qm+1 in Q
  for each a in Sigma union {epsilon}
  for each A,B1,B2,B3,...,Bm in Gamma
  such that there is a delta of the form

    delta(qi,a,A) = { ...,(qj,B1B2B3...Bm), ...}

  Note three degenerate cases:

           delta(qi,a,A)=phi  makes no productions

           delta(qi,a,A)={(qj,epsilon)} makes [qi,A,qj] -> a

           delta(qi,epsilon,A)={(qj,epsilon)} makes [qi,A,qj] -> epsilon


  The general case:

  Pictorially, given  delta(qi,a,A)= (qj,B1B2)   generate the set
                            |  | |    |  | |     for qk being every state,
              +-------------+  | |    |  | |     while qm+1 is every state
              |  +---------------+    |  | |
              |  |             |      |  | |
              |  |          +--+      |  | |
              |  |          | +-------+  | |
              |  |          | |  +-------+ |
              |  |          | |  |         |
              V  V          V V  V         V
             [qi,A,qm+1] -> a[qj,B1,qk][qk,B2,qm+1]
                   |                |   ^     ^
                   |                |   |     |
                   |                +---+     |
                   +--------------------------+

  The book suggests to follow the chain of states starting with the right
  sides of the S -> productions, then the new right sides of the [q,a,p] ->
  productions. The correct grammar is built generating all productions.
  Then the "simplification" can be applied to eliminate useless variables,
  eliminate nullable variables, eliminate unit productions, convert to
  Chomsky Normal Form, convert to Greibach Normal Form.

  WOW! Now we have the Greibach Normal Form of a NPDA with any number of
  states and we can convert this to a NPDA with just one state by the
  construction in the previous lecture.

  The important concept is that the constructions CFG to NPDA and NPDA to CFG
  provably keep the same language being accepted. Well, to be technical,
  The language generated by the CFG is exactly the language accepted by
  the NPDA. Fixing up any technical details like renaming Gamma symbols
  if Gamma intersection Sigma not empty and accepting or rejecting
  the null string appropriately.

  The reverse of the example in the previous lecture. |Q|=1 makes it easy.
  Given: NPDA = (Q, Sigma, Gamma, delta, q0, Z0, F)
         Q={q} Sigma={0,1} Gamma={C,S,T} q0=q  Z0=S  F=Phi
         delta(q, 0, C) = (q, CT)
         delta(q, 0, C) = (q, TT)
         delta(q, 0, S) = (q, C)
         delta(q, 0, S) = (q, T)
         delta(q, 1, T) = (q, epsilon)

  Build: G = (V, T, P , S)
         V = { S, qCq, qSq, qTq }  four variable names
         T = Sigma = {0, 1}        (dropping the previous punctuation [,,])
         S = Z0 = S
  S-> productions
         S -> qSq       Note!  qSq is a single variable 
                               just dropped the [,, ] symbols

  other productions:
       delta(q, 0, C)  =  (q, CT)
             |  |  |       |  ||
       +-----+  |  |  +----+  ||
       |+----------+  |+------+|
       ||       |     ||     +-+
       ||       |     ||     |
       qCq  ->  0     qCq   qTq       was  C -> 0 C T
         |              |   | |
         |              +---+ |    
         +--------------------+

  continue using same method on each delta:
      qCq -> 0  qTq  qTq
      qSq -> 0  qCq
      qSq -> 0  qTq
      qTq -> 1                 (epsilon becomes nothing)

  Now, if you prefer, rename the variables to single letters
  (assuming you have a big enough alphabet)
  For this simple example  qCq becomes just C, qSq becomes just S
  and qTq becomes just T, thus the productions become:
      C -> 0  C  T
      C -> 0  T  T
      S -> 0  C
      S -> 0  T
      T -> 1

  This grammar is Greibach normal form for L(G)={0^n 1^n | n<0}

Now, working an example for another NPDA for this same language:

  NPDA  M = ( Q, Sigma, Gamma, delta, q0, Z0, Phi)
  Q = { q0, q1 }
  Sigma = { 0, 1 }
  Gamma = { Z0, V0, V1 }
  delta =
          (q0,0,Z0) = (q0,V0)      pop Z0 write V0 (for zero)
          (q0,0,V0) = (q0,V0V0)    add another V0 to stack
          (q0,1,V0) = (q1,epsilon) pop a V0 for a one
          (q1,1,V0) = (q1,epsilon) pop a V0 for each 1
  accept on empty stack

  Build: G = (V, T, P , S)
         V = { S, see below in productions }  
         T = Sigma = {0, 1} 
         S = Z0 = S

  S-> productions
       S -> [q0,Z0,q0]  (one for each state)               P1
       S -> [q0,Z0,q1]                                     P2

  delta productions
          (q0,0,Z0) = (q0,V0)  (one for each state)

          [q0,Z0,q0] -> 0 [q0,V0,q0]                       P3
                  |               |
                  +---------------+

          [q0,Z0,q1] -> 0 [q0,V0,q1]                       P4
                  |               |
                  +---------------+

          (q0,0,V0) = (q0,V0V0)  (two combinations of two states)


          [q0,V0,q0] -> 0 [q0,V0,q0] [q0,V0,q0]            P5
                  |               |    |     |
                  |               +----+     |
                  +--------------------------+

          [q0,V0,q0] -> 0 [q0,V0,q1] [q1,V0,q0]            P6
                  |               |    |     |
                  |               +----+     |
                  +--------------------------+

          [q0,V0,q1] -> 0 [q0,V0,q0] [q0,V0,q1]            P7
                  |               |    |     |
                  |               +----+     |
                  +--------------------------+

          [q0,V0,q1] -> 0 [q0,V0,q1] [q1,V0,q1]            P8
                  |               |    |     |
                  |               +----+     |
                  +--------------------------+

          (q0,1,V0) = (q1,epsilon)

          [q0,V0,q1] -> 1                                  P9

          (q1,1,V0) = (q1,epsilon)

          [q1,V0,q1] -> 1                                  P10

A a brief check, consider the string from the derivation
    P2, P4, P9  that produces the string  01

    P2, P4, P8, P9, P10  that produces the string  0011