This shows all the productions needed to justify membership; these can
then be used in the parsing
Chapter 7
Section 7.1
2. The key to the argument is the switch from q 0 to q 1 , which is done
nondeterministically and need not happen in the middle of the string.
However, if a switch is made at some other point or if the input is notof the
form ww R , an accepting configuration cannot be reached. Suppose the
content of the stack at the time of the switch is x 1 x 2 …x k z. To accept a string
we must get to the configuration (q 1 , λ, z). By examining the transition
function, we see that we can get to this configuration only if at this point the
unread part of the input is x 1 x 2 …x k , that is, if the original input is of the form
ww R and the switch was made exactly in the middle of the input string.
4. (a) The solution is obtained by letting each a put two markers on the stack,
while each b consumes one. Solution:
(f) Here we use nondeterminism to generate one, two, or three tokens by