3.4 Pushdown Automata 131
path of your PDA on X.(a) {unbm 1 m,n > 0,m # 3n); x = a2b4.
(b) {unbm IO < 2; < m < 3n); x = a2b5.
(c) {unbm IO 2 2n 2 3m< 4n - 2); x = a3b3
(d) (a%+ 1 i,j, k CO, i +-2lc = j}; x = u3b7c2.
(e) {ua’bjck 1 i,j, k > 0,2i + 3k < 4j); x = u4b4c2.
(f) {c&c”d’ 1 i,j, i> 0, i + k Tj + I}; x = u2b4c5d3.
(g) {ui@ckdl I i,j, k 5 0,2i + 3i 5 4j + I}; x = u3b4c4d5.
(h) {w E {u, b}* I2#a(w) + 5 < 3#b(~)}; x = ubbubbu.
(i) {w E {u,b}* I2#&v) 5 3#b(w) 5 4#,(w)}; x = ubbuuub.
(j) {w E {a, b, c}* 1 Sjta(w) 5 #b(w) + 3#,(w)}; x = uacddha.
* (k) Iw E b, b,c}* 1 2#c&) 5 #b(W) + 3#c(w) 5 5#a(w)}; X =
ucubcc.- In Example 3.32, when we finished processing the input symbols, we
move to one of the final states p, or pb if the stack is nonempty. Show
that the two separate states are necessary. That is, suppose we merge
states pa and pb of Figure 3.15 into a single final state p, with the
instructions
J(s, E, a) = J(s, E, b) = J(p, E, a> = S(p, E, b) = (p, E).Show that, then, the new PDA would accept some strings not in L.
- Show that each of the following variations of the pushdown automaton
model is equivalent to our original definition of pushdown automata, in
the sense that the class of languages accepted by pushdown automata
remains the same.
( > a
(b)( 1 C
The PDA is allowed to push two stack symbols into the stack in
one move; that is, the transition function S is a function of the
following form:S : Q x (C u {E}) x (I’u {E}) + 2Qx(+1urur2).
The PDA is allowed to push any number of stack symbols into the
stack in one move; that is, the transition function 6 is a function
of the following form:S : Q x (C u {E}) x (I’ u {E}) + 2Qxr*.
The PDA is required to pop up the top element of the stack at
each move and is allowed to push two stack symbols into the stack
in one move; that is, the transition function S is a function of the
following form:S : Q x (C u {E}) x I’ + 2QX(+~urur2).