we use the fact that the symbols are retrieved from a stack in the reverse order of
their insertion. When reading the first part of the string, we push consecutive
symbols on the stack. For the second part, we compare the current input symbol
with the top of the stack, continuing as long as the two match. Since symbols are
retrieved from the stack in reverse of the order in which they were inserted, a
complete match will be achieved if and only if the input is of the form ww R .
An apparent difficulty with this suggestion is that we do not know the middle
of the string, that is, where w ends and w R starts. But the nondeterministic nature
of the automaton helps us with this; the npda correctly guesses where the middle
is and switches states at that point. A solution to the problem is given by M = (Q,
Σ, Γ, δ, q 0 , z, F), where
Q = {q 0 , q 1 , q 2 },
Σ = {a,b},
Γ = {a, b, z},
F= {q 2 }.
The transition function can be visualized as having several parts: a set to
push w on the stack,
a set to guess the middle of the string, where the npda switches from state q 0 to
q 1
a set to match w R against the contents of the stack,