CFG/CFL to NPDA

 Given a Context Free Grammar, CFG, in Greibach Normal Form, A -> aB1B2B3...
  Construct an NPDA machine that accepts the same language as that grammar.

  We are given G = ( V, T, P, S ) and must now construct
  M = ( Q, Sigma, Gamma, delta, q0, Z0, F) 
  Q = {q}  the one and only state!
  Sigma = T
  Gamma = V
  delta is shown below
  q0 = q
  Z0 = S
  F  = Phi  NPDA will "accept on empty stack"

  Now, for each production in P (individual production, no vertical bars)

       A -> a gamma  constructs
       |    |   |
       |    |   +-------------+
       |    |                 |
       +-----------+          | gamma is a possibly empty, sequence of
            |      |          |       symbols from Gamma
            +---+  |          |
                |  |          |
                V  V          V
       delta(q, a, A) = {(q, gamma), more may come from other productions}

  If gamma is empty, use epsilon as in (q, epsilon)
  Finished!

  An example:  Given production      Resulting delta             #
               C -> 0 C T            delta(q, 0, C) = (q, CT)    1
               C -> 0 T T            delta(q, 0, C) = (q, TT)    2
               S -> 0 C              delta(q, 0, S) = (q, C)     3
               S -> 0 T              delta(q, 0, S) = (q, T)     4
               T -> 1                delta(q, 1, T) = (q, #e)    5

  NPDA running with input tape 0011 and initial stack S
       0011      |S|
       ^         | |

  delta #3 and #4 both apply, resulting in two stacks and advancing input
       0011      |C|         |T|
        ^        | |         | |

  delta #1 and #2 apply to the first stack, the second stack dies, advancing
       0011      |C|   |T|  dies
         ^       |T|   |T|
                 | |   | |

  delta #5 applies to the second stack, the first stack dies, advancing
       0011     dies   |T|
          ^            | |
  delta #5 applies, the stack becomes empty and advance to beyond input
       0011            | |
           ^           | |
  accept input string.

Another conversion algorithm that uses more states, three to be exact,
is somewhat simpler.

  We are given G = ( V, T, P, S ) and must now construct

  M = ( Q, Sigma, Gamma, delta, q0, Z0, F) 
  Q = {q0, q1, q2}
  Sigma = T
  Gamma = V union {Z} where Z not in V (an extra symbol)
  delta = Q x (Sigma union epsilon) x Gamma -> Q x Gamma  shown below
  q0 = q0
  Z0 = Z  (to get the NPDA started)
  F  = q2  the final accepting state

  Two predefined transitions, the start and the accept are:
  delta(q0, epsilon, Z) = { (q1, SZ) }
  delta(q1, epsilon, Z) = { (q2, Z) }

  For every rule in P , Greibach normal form, A -> aU generate
  delta(q1, a, A) = { (q1, U) } union all other sets from (q1, a, A)

  Note: The empty string must be removed to create Greibach normal form,
  thus a grammar that initially accepted the empty string needs the
  extra transition
  delta(q0, epsilon, Z) = { (q2, Z) }

  The conversion is proved to simulate a leftmost derivation.