Problem Solving in Automata, Languages, and Complexity

3.4 Pushdown Automata 125

b,E a, E/a Lb

Figure 3.12: Solution to Example 3.29.

Example 3.29 Construct a PDA accepting the language {wwR 1 w E
-ia, b)1
Solution. This example is similar to the last one, except that the input does
not have a middle separator c, and so we do not know when to start the
comparison between the input and the stack. How do we attack this prob-
lem? We recall that PDA’s are nondeterministic machines. Thus, we may
nondeterministically start the comparison at any point. An input string is
then accepted as long as the remaining input symbols match correctly with
the stack symbols with respect to some separating point.
According to this idea, a PDA is constructed in Figure 3.12. We show
three computation paths on input abba; the first one accepts, and the other
two move to state p at the wrong time and reject.

(4, abba, E) t-- (a, bba, a> I- (a, ba, ba) I- (P, ba, q I- (p, a, a) I- (p, E, E);

(q, abba, E) I- (4, bba, a) I- (q, ba, ba) I- (4, a, bba) I- (p, a, bba);

(qdba, E) t- (cl, bba, a) I-- (P, bb a>.

Example 3.30 Construct a PDA that accepts the language

{a”b-k” 1 i,j, k > 0, i + k = j}. -

Solution. The basic idea for this problem is to use different states to enforce
the order of the occurrences of the letters a, b and c, and use the stack to
meet the requirement of i + k = j. Therefore, we construct a PDA M with
three states s, q, p, where s is the initial state and p is the unique final state.
At state s, M pushes each input symbol a into the stack. At state q, M reads
each input symbol b and either matches the symbol b with a symbol a in the
stack or pushes the symbol b into the stack. At state p, it reads a symbol c
and matches it with a symbol b in the stack. The transition diagram of the
complete PDA is shown in Figure 3.13.
Like the last example, this PDA M moves nondeterministically from state
s to state q and from state q to state p. Therefore, there may be many
different computation paths for the same input. There is, however, at most
one accepting path which changes states when input changes symbols. 0

Example 3.31 Construct a PDA that accepts the language

L = {c-w I2i # 3j).