// wwr.npda  code an NPDA for:
// language  { w wr | wr is string w in reverse order w = {0, 1} }
// CGF  S -> 00    strict form, even length
//      S -> 11
//      S -> 0S0
//      S -> 1S1
//
// Chomsky Normal Form
//  S -> A C
//  S -> A A
//  S -> B D
//  S -> B B
//  A -> 0
//  B -> 1
//  C -> S A
//  D -> S B
//
// Greibach Normal Form (almost)
//  S -> 0 C
//  S -> 0 A
//  S -> 1 D
//  S -> 1 B
//  A -> 0
//  B -> 1
//  C -> S 0
//  D -> S 1
//
// 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
q0 #e  0   q1  0
q0 #e  1   q1  1
q1  0  0   q1  #e  // has popped stack, no push
q1  1  1   q1  #e  // has popped stack, no push
q1 #e  Z   q2  Z   // accept, done

enddef

tape 110001100011  // accept

tape 00000         // reject, odd number of input characters