δ (q 2 ,a)=(q 2 ,a,L),
δ (q 2 ,x)=(q 0 ,x,R),
We are now back in the initial state q 0 , ready to deal with the next a and b.
After one pass through this part of the computation, the machine will have
carried out the partial computation
so that a single a has been matched with a single b. After two passes, we will
have completed the partial computation and so on, indicating that the matching
process is being carried out properly.
When the input is a string a n b n , the rewriting continues this way, stopping
only when there are no more a’s to be erased. When looking for the leftmost a,
the read-write head travels left with the machine in state q 2 . When an x is
encountered, the direction is reversed to get the a. But now, instead of finding an
a it will find a y. To terminate, a final check is made to see if all a’s and b’s have
been replaced (to detect input where an a follows a b). This can be done by
δ (q 0 ,y)=(q 3 ,y,R),
δ (q 3 ,y)=(q 3 ,y,R),
δ (q 3 , )=(q 4 , ,R),
If we input a string not in the language, the computation will halt in a
nonfinal state. For example, if we give the machine a string a n b m , with n > m, the
machine will eventually encounter a blank in state q 1 . It will halt because no
transition is specified for this case. Other input not in the language will also lead
to a nonfinal halting state (see Exercise 3 at the end of this section).
The particular input aabb gives the following successive instantaneous
descriptions:
δ (q 2 ,x)=(q 0 ,x,R),
We are now back in the initial state q 0 , ready to deal with the next a and b.
After one pass through this part of the computation, the machine will have
carried out the partial computation
so that a single a has been matched with a single b. After two passes, we will
have completed the partial computation and so on, indicating that the matching
process is being carried out properly.
When the input is a string a n b n , the rewriting continues this way, stopping
only when there are no more a’s to be erased. When looking for the leftmost a,
the read-write head travels left with the machine in state q 2 . When an x is
encountered, the direction is reversed to get the a. But now, instead of finding an
a it will find a y. To terminate, a final check is made to see if all a’s and b’s have
been replaced (to detect input where an a follows a b). This can be done by
δ (q 0 ,y)=(q 3 ,y,R),
δ (q 3 ,y)=(q 3 ,y,R),
δ (q 3 , )=(q 4 , ,R),
If we input a string not in the language, the computation will halt in a
nonfinal state. For example, if we give the machine a string a n b m , with n > m, the
machine will eventually encounter a blank in state q 1 . It will halt because no
transition is specified for this case. Other input not in the language will also lead
to a nonfinal halting state (see Exercise 3 at the end of this section).
The particular input aabb gives the following successive instantaneous
descriptions: