Push Down Automata, PDA, NPDA

Push Down Automata, PDA, are a way to represent the language class called
 Context Free Languages, CFL, covered above. By themselves PDA's are not
 very important but the hierarchy of Finite State Machines with
 corresponding Regular Languages, PDA's with corresponding CFL's and
 Turing Machines with corresponding Recursively Enumerable Sets (Languages),
 is an important concept.

 The definition of a Push Down Automata is:
 M = (Q, Sigma, Gamma, delta, q0, Z0, F)  where
 Q = a finite set of states including q0
 Sigma = a finite alphabet of input symbols (on the input tape)
 Gamma = a finite set of push down stack symbols including Z0
 delta = a group of nondeterministic transitions mapping
         Q x (Sigma union {epsilon}) x Gamma to finite sets of Q x Gamma star
 q0 = the initial state, an element of Q, possibly the only state
 Z0 = the initial stack contents, an element of gamma, possibly the only
      stack symbol
 F = the set of final, accepting, states but may be empty for a PDA
     "accepting on an empty stack"

 Unlike finite automata, the delta is not presented in tabular form.
 The table would be too wide.  Delta is a list of, nondeterministic,
 transitions of the form:
   delta(q,a,A) = { (qi,gammai), (qj,gammaj), ...}  where
   q is the current state,
   a is the input tape symbol being read, an element of Sigma union {epsilon}
   A is the top of the stack being read,
   The ordered pairs (q sub i, gamma sub i) are respectively the next state
   and the string of symbols to be written onto the stack. The machine
   is nondeterministic, meaning that all the pairs are executed causing
   a branching tree of PDA configurations. Just like the branching tree
   for nondeterministic finite automata except additional copies of the
   pushdown stack are also created at each branch.

 The operation of the PDA is to begin in state q0, read the symbol on the
 input tape or read epsilon. If a symbol is read, the read head moves
 to the right and can never reverse to read that symbol again.
 The top of the stack is read by popping off the symbol.
 Now, having a state, an input symbol and a stack symbol a delta transition
 is performed. If there is no delta transition defined with these three
 values the machine halts. If there is a delta transition with the (q,a,A)
 then all pairs of (state,gamma) are performed. The gamma represents a
 sequence of push down stack symbols and are pushed right to left onto
 the stack. If gamma is epsilon, no symbols are pushed onto the stack. Then
 the machine goes to the next state, q.

 When the machine halts a decision is made to accept or reject the input.
 If the last, rightmost, input symbol has not been read then reject.
 If the machine is in a final state accept.
 If the set of final states is empty, Phi, and the only symbol on the stack
 is Z0, then accept. (This is the "accept on empty stack" case)


 Now, using pictures we show the machines for FSM, PDA and TM

 +-------------------------+----------------- DFA, NFA, NFA epsilon
 | input string            |                  accepts Regular Languages
 +-------------------------+----------------- 
    ^ read, move right
    |
    |  +-----+
    |  |     |--> accept
    +--+ FSM |                   M = ( Q, Sigma,        delta, q0,    F)
       |     |--> reject
       +-----+

 +-------------------------+----------------- Push Down Automata
 | input string            |Z0  stack         accepts Context Free Languages
 +-------------------------+-----------------
    ^ read, move right      ^ read and write (push and pop)
    |                       |
    +-----------------------+
    |  +-----+
    |  |     |--> accept
    +--+ FSM |                   M = ( Q, Sigma, Gamma, delta, q0, Z0, F)
       |     |--> reject
       +-----+

 +-------------------------+-----------------  Turing Machine
 | input string            |BBBBBBBB ...       accepts Recursively Enumerable
 +-------------------------+-----------------  Languages
    ^ read and write, move left and right
    |
    |  +-----+
    |  |     |--> accept
    +--+ FSM |                   M = ( Q, Sigma, Gamma, delta, q0, B,  F)
       |     |--> reject
       +-----+


  An example of a language that requires the PDA to be a NPDA,
  Nondeterministic Push Down Automata,
  is L = { w wr | w in Sigma and wr is w written backwards }

// wwr.npda  code an NPDA for:
// language  { w wr | wr is string w in reverse order w = {0, 1} }
// CGF  S -> 00   # strict form, must have even length 
//      S -> 11
//      S -> 0S0
//      S -> 1S1
//
// remember, nondeterministic, do all applicable transitions in parallel
//           create multiple stacks as needed, some of the parallel may die
//
// NPDA = (Q, sigma, gamma, delta, Q0, Z0, F)
//         Q = {q0, q1, q2}   states
//         sigma = {0, 1}     input tape symbols (#e is empty string, epsilon)
//         gamma = {0, 1, Z}  stack symbols
//         delta = {(Q x sigma x gamma_pop) to (Q x gamma_push) ...
//                                             nondeterministic transitions
//         Q0 = q0            starting state
//         Z0 = Z             starting stack symbol
//         F = {q2}           final state

start q0
final q2
stack Z    // saves typing Z0, initially on stack

// state, input-read, top-of-stack-popped, go-to-state, push-on-stack 

q0  0  Z   q0  0Z  // first 6 just push input onto stack
q0  1  Z   q0  1Z
q0  0  0   q0  00
q0  0  1   q0  01
q0  1  0   q0  10
q0  1  1   q0  11
q0 #e  Z   q1  Z   // these 3 keep trying to find middle, most die
q0 #e  0   q1  0   // tried after every input symbol
q0 #e  1   q1  1
q1  0  0   q1  #e  // matching input to stack, has popped stack, no push
q1  1  1   q1  #e 
q1 #e  Z   q2  Z   // accept, done

enddef

tape 110001100011  // accept, w = 110001

tape 00000         // reject, odd number of input characters