Problem Solving in Automata, Languages, and Complexity

124 CONTEXT-FREE LANGUAGES

b,c a, E/a /b

Figure 3.11: Transition diagram of PDA M of Example 3.28.

c = (p, y, y) and Ci t- Ci+l for all i = 0, 1,... , n - 1.

(; c

A sequence

0, l,***, Cn) of configurations of M is a computation path of M if CO

is an initial configuration (s, X, E), Cn does not have a successor configuration,

andC+Ci+lforalli=O,l,...,n- 1. We recall again that M is, in general,

nondeterministic and so it may have more than one computation path starting

from the same initial configuration. In addition, a configuration (a, X, ,0) may

have no successor configuration, even if IX: # &.

Now, we can define formally the notion of a PDA M accepting a string

x E C* as follows: M accepts z if and only if there is a computation path of

M that starts with the initial configuration (s, X, E) and ends at a configuration

(f, E, E) for some f E F; that is,

ww = ix E c* I (3 E F) [(St x, E) p (f, 6 E)]}.

For instance, the following are three computation paths of the machine M
of Example 3.28 on inputs abcba, abcb, and abcbab.

(a, abcba, 4 t- (CL bcba, a) t- (!Lcbba) t- (P, boa) t- (P, a, a> t- (P, 6 g;

(4, abcb, 4 t- (q,bcb,a) I-- (4, cb, ba) t- (P, hba) t- (P, G a>;

(q, abcbab, E) I-- (q, bcbab, a) I- (q, cbab, ba) I- (p, bab, ba) k (p, ab, a) I- (p, b, E).

Note that in. the second computation path, the m achine M rejects since the

stack is not empty when M finishes reading the input symbols. In the third

computation path, it rejects because the configuration (p, b, E) does not have

a successor configuration, and yet the input is not completely read.

A pushdown automaton may also be represented, as an NFA, by its tran-

sition diagram. In the transition diagram of a PDA, each vertex represents a

state and each edge from vertex q to p with label “a, U/V” represents a tran-

sition (p,v) E S(q,a,u). For example, the PDA M of Example 3.28 can be

represented by the transition diagram of Figure 3.11.

It is worth mentioning that in the transition diagram of a DFA or an NFA, a

path from the initial state to a final state represents an accepting computation

path, but it is not the case for PDA’s. It is easy to find a path from the initial

state q to the final state p in Figure 3.11 which does not represent an accepting

computation path. Actually, such a path in the transition diagram may not

even represent a legal computation path. A legal computation path of a PDA

must take into account the correct stack information.