Problem Solving in Automata, Languages, and Complexity

306 COMPUTATIONAL COMPlJ3XITY

/

0-T

\

a6

Figure 6.7: The computation tree of M on input X.

a0 = (s, a2baba3ba2bba4@ I- (qo, a2baba3ba2bba3a)

P (aI, a2baba3ba2bba4) t (q2, a2baba3baacba4) - = al.

At this point, al has two successor configurations which lead to two different
paths in the computation tree:

~1 t (q3, a2baba3baacba4) - F (q2, a2baba2ga2cba4) = a2,

al t (q4, a2baba3bac2ba4) - P (q2, a2baba2ac4ba4) - = CQ.

Similarly, CQ has two successor configurations:

CQ t (q3, a2babagaca2cba4) F (q2, a2bgca3ca2cba4) = ~4,

CQ t (44, a2babagc2a2cba4) F (42, a2bgc5a2cba4) = CQ.

Also, a3 has two successor configurations

a3 t (q3, a2babagac4ba4) c (q2, a2bgca3c4ba4) = a&

a3 t (q4, a2babagc5ba4) p (q2, a2bgc8ba4) = CQ.

Each of CY~, ~25, @, and ~27 then has
We leave the rest of the computation

two

tree

successor configurations, and so on.
to the reader. The general str ucture
of the computation tree is as shown in Figure 6.7.^0

We make an important observation about the above nondeterministic al-
gorithm. The algorithm consists of two stages: the guessing stage and the
verification stage. In the guessing stage, it makes a number of nondetermin-
istic guesses to create a specific configuration among many possible choices.
For instance, with the input x defined in the above example, a specific config-
uration (qs, aac7a2cba4) - could be created by guessing that A = { 1,4}. In the
verification stage, it verifies deterministically that the configuration obtained
in the first stage satisfies the condition that there are an equal number of sym-
bols a to the left and to the right of b. For instance, it accepts the configuration
( q5, gc7a2 cba4) deterministically. Indeed, many useful nondeterministic al-
gorithms can be devised using this two-stage construction method. We call