6.4 Nondeterministic Turing Machines 305
a b c B
S 40, B, L
qo qo4,L !Il,hL
Ql 421 c, L
42 43,aJ 42,cJ
44, c, L
q3 43,aJ 42&J 45, B, R
q4 4414 q2, c, L q5, B, R
q5 q6,B,R q9,B,R qGB,R
q6 q6,%R q?,hR q6>C,R
q7 Q8,CJ q7, c, R (reject)
q8 qa,a,L Q8AL QSAL 45AR
q9 (reject) q9AR h,B,R
Figure 6.6: The transition function of machine AL
Example 6.22 Let L= {a”lbai2b-•baikbbaj 1 il,...,ik,j >0, ~,.J,- =j
forsomeAC{1,2,.. -. , k}}. Find an NTM accepting the language L.
Proof. A string ai1 bai2b. l l baikbbaj is in L if there are a number of a-blocks
before bb whose total size is equal to the last a-block (after bb). A straight-
forward deterministic algorithm may have to check this condition over all
possible subsets of a-blocks, which would take at least 2” moves.
On the other hand, with a nondeterministic machine, we can just guess a
subset A C - (1,.. ., k} of a-blocks and then verify that the total size of the
a-blocks in the subset A is equal to j. More precisely, we first move the tape
head to the left passing the double-b mark. Then, for each block of symbols
a, we nondeterministically decide either to keep it as it is or to change each
symbol a in the block to the symbol c. When we reach the left-end blank, we
move back toward right and behaves like a deterministic TM that compares
the number of a’s to the left of double-b with the number of a’s to the right.
It accepts the input if the two sides have an equal number of a’s. We show the
transition function of M in Figure 6.6. (For convenience, we actually change,
in the first round, the double-b into a single b and all other b’s into c’s.)
Note that this algorithm creates 2” paths in the computation tree, and most
of them would reject the input. However, the input is considered accepted
as long as one computation path accepts it. For instance, consider the input
x= aababaaabaabbaaaa (i.e., il = i4 = 2, i2 = 1, i3 = 3 and j = 4). If we
select the first and fourth blocks to match with aj, or if we select the second
and third blocks to match with aj, then these computation paths accept. All
other 14 paths reject.
To be more precise, let us examine this computation tree more carefully.
At first, the computation has a unique path:
