AnBn Machine and Traces
|
On
this page and the next we illustrate two specific Turing Machines.
The first is designed to accept the set of strings that can be
formed by writing down n A's followed by n
B's where n > 0. In the context of the theory of machines
or automata, such a set is typically referred to as the language
accepted by some machine M. A machine is said to accept
a language if the machine reaches a halt state for all strings
in the language and does not reach a halt state for all strings
not in the language. That is, the machine accepts all
and only the strings of the language.
This
particular language is an example of a very simple language that
cannot be recognized by a Finite State Machine. Recall that we
have illustrated FSM that accept languages similar to this; for
example n A's followed by n B's where 0
< n < 4. The difference, of course, is that
in these languages a bound on n is specified. Within
an FSM the control states provide the only basis for "remembering"
aspects of the computation being carried out by the machine.
For example, if the language is defined such that there must
be at least one A in the string before a B occurs then a control
state must be introduced to insure that this constraint is satisfied
by the input string.
The
Turing Machine illustrated here accepts the language by controlling
its movement on the tape and erasing the tape contents to "remember"
whether it has seen a pair of A's and B's. You may have expected
that we would write a machine that simply counted the number
of A's and B's on the tape and then checked whether the resulting
counts were equal. This could be done, and since most programming
languages provide the programmer with a data type, integers,
together with the necessary operation to count , +1, and predicate,
=, on integers, it would be trivial to do it in this way.
But, recall that the only data type known to a Turing Machine
are strings. This is sufficient since we can easily define a
function that maps the integers into sets of strings. Such a
function is exemplified in the figure shown below.
|
|
In
this figure the integers are shown in the gray oval and the arrows
illustrate the correspondence between the integer and a string
of symbols, in this case a string of vertical marks shown in
the yellow oval. The operation of +1 could be realized using
a TM that found the end of the string of marks and then placed
an additional mark at the end. It is interesting to note that
the TM that realized the equality predicate would look much the
same as the machine that will be illustrated here. This is not
surprising since the constraint of equality of A's and B's is
one of the constraints that must be checked by a machine that
accepts the language of n A's followed by n
B's.
On
another page we will consider a machine that accepts the language
consisting of n A's followed by n B's followed
by n C's where n > 0. In this case you
will see that we must introduce explicitly the idea of maintaining
a count of n in order to realize this machine. It turns
out that one doesn't really need a TM to accept the language
of n A's followed by n B's; a machine called
a pushdown automata can do the job. However, a TM is required
to accepts the language consisting of n A's followed
by n B's followed by n C's; and this result
is related to the necessity of maintaining the count of n.
|
 |
| The
table to the right displays the form of the rules or tuples that
will be used in these examples. The first two elements of the
table represent the condition portion of the rule and include
the now familiar pair; the current control state of the machine
together with the symbol on the input tape that is currently
under the read head. |
| current
control state |
current
symbol |
new
symbol |
action |
new
control state |
|
| The
last two elements of the table, the action and new control state
are again familiar. However, in the form of the Turing Machine
used here we allow the rule to specify a write operation, the
third element of the table, as well as an action. This does not
give the machine any more power, but it does often allow us to
use fewer control states to represent a machine that computes
a particular function. |
|
The
table to the right lists the set of rules that define the TM
that accepts the language consisting of n A's followed
by n B's where n > 0. q0 is the start state and qh is the
halt state. The first rule states that 'if the current control
state is q0 and
the current symbol under the read head is A, then write # (the
symbol we use here for blank) and move the read head to the right
(R) and make q2
the current control state.' The
figure below this table of rules presents the same information
in the form of a graph. For example, the first rule is represented
in the graph by the connection between the green node labeled
q0 and
the blue node labeled q2. The 'A / # R' over the arrow specifies
the rest of the rule. Ten rules and six control states are used
in this TM. The write action involves "erasing" the
A and B elements of the string systematically. By erasing
the elements in pairs the machine can carry out the required
test of determining whether there are an equal number of A's
and B's.
Note
that the erasure of an A always occurs prior to the erasure of
a B. An A is erased initially on the transition from q0 to q2. This
transition also ensures that the empty string is not accepted.
q2 controls
the traversal of the input string to its end. When the end is
encountered a transition to q3 is made. Notice that the only instruction
involving q3
requires that a B is under the read head. When the rule is applied,
B is erased and a transition to q4
is made. The rules associated
with q4 serve
to return the read head to the left or beginning of the input
string. .
|
Tuples
| current
control state |
symbol
under read head |
new
symbol |
action |
new
control state |
| q0 |
A |
# |
R |
q2 |
| q2 |
A |
A |
R |
q2 |
| q2 |
B |
B |
R |
q2 |
| q2 |
# |
# |
L |
q3 |
| q3 |
B |
# |
L |
q4 |
| q4 |
A |
A |
L |
q4 |
| q4 |
B |
B |
L |
q4 |
| q4 |
# |
# |
R |
q1 |
| q1 |
A |
# |
R |
q2 |
| q1 |
# |
# |
S |
qh |
|
|
If an A is encountered at q1 then the
cycle is repeated. If only blanks remain, then the equality constraint
has been satisfied and the machine moves to the halt state, qh
The
remainder of the page contains a set of tables on which the operation
of this TM is traced together with an animation of one of these
traces.
Consider
first the trace on the left which is entitled "Testing String
AB#". Below this row are 6 numbered lines which present
a view of the TM at each of these steps in the process. The second
segment of each of these rows contains the tape contents at that
step in the trace. The character that is underlined and shown
in red is the character of the string that is under the read
head at this step in the trace. The last segment of the row lists
the rule or tuple that was applied on this step.
|
 |
Consider
the first row. This is step 01 or the beginning of the trace.
The read head is at the left of the tape over character A and
the string on the tape at this point is AB#. The current state is q0. Therefore the rule that applies at
this point is
'q0 A # R q2'. The
tape content at step 02 is #B# reflecting that A has been erased and
the read head moved according to the actions expressed in the
rule applied at step 01. The tape content at step 03 is #B# and the end of the sequences of characters
on the tape is recognized and the read head is moved to the left.
Step 04 then erases the B and the remaining steps check that the
tape is not empty of characters. |
AB# Trace
| Testing String AB# |
01 - AB#
- q0 A # R q2
02 - #B# - q2 B B R q2
03 - #B# - q2 # # L q3
04 - #B# - q3 B # L q4
05 - ### - q4 # # R q1
06 - ### - q1 # # S qh |
| AB# was ACCEPTED. |
|
|
The
animation to the right illustrates the operation of this TM on
input of AABB#. It is displayed above the table of the trace
to further help you to visualize the way in which this algorithm
is realized.
The
remaining traces illustrate the actions of this TM when strings
AAAABBBB#, AAAAABBBBB#, and AAAAABBBBB# are input to this TM.
|
 |
|
Rather
than placing these traces directly on the page, a thumbnail of
each of these traces is provided below on the right. Clicking
on the thumbnail will result in opening a pop-up window with
an enlarged version of the trace. Clicking on this main window
will close the pop-up window.
Note
that these traces represent the entire history of a computation
for a particular input string. Consider step 01 as shown in the
AAAABBBB# trace. Here the string is 'AAAABBBB#'. Recall from the Machine
Chapter that rewriting this as "A<q0>AAABBBB#"
illustrates what is referred
to as the instantaneous description of the machine. From
these traces you can see that the tuples together with these
instantaneous descriptions provide all of the information required
to specify the actions of a TM. And, both the rules and the instantaneous
descriptions are simply strings of symbols which themselves could
be represented on a tape. With this in mind it may be a little
easier to envisage the possibility of a universal TM.
|
AABB# Trace
| Testing String AABB# |
01 - AABB#
- q0 A # R q2
02 - #ABB# - q2 A A R q2
03 - #ABB# - q2 B B R q2
04 - #ABB# - q2 B B R q2
05 - #ABB# - q2 # # L q3
06 - #ABB# - q3 B # L q4
07 - #AB## - q4 B B L q4
08 - #AB## - q4 A A L q4
09 - #AB## - q4 # # R q1
10 - #AB## - q1 A # R q2
11 - ##B## - q2 B B R q2
12 - ##B## - q2 # # L q3
13 - ##B## - q3 B # L q4
14 - ##### - q4 # # R q1
15 - ##### - q1 # # S qh |
| AABB# was ACCEPTED. |
|
|
Another
feature to note is that the length of the trace increases with
the length of the input string. For example, the top row of the
table at the bottom of this page records the length of the input
string and the second row lists the number of steps in the associated
trace.
Recall
the discussion in the Machine
Chapter on the use of the Turing Machine model as a "yardstick
to measure just how complex it is to solve a particular kind
of problem." There are two measures of interest. One is
the amount of space required. And the other is the number of
steps. In both cases what we seek is an equation that specifies
these values as a function of the size of the input string. If
such equations can be found then this algorithm could be compared
to another which computed this same function.
Consider the present algorithm.
Shifting our naming of variables slightly we can say that this
algorithm accepts any input string that consists of j
A's followed by j B's. Thus, the length of the input string,
n, for this language of A's followed by an equal number
of B's is simply 2j.
|
 |
 |
 |
AAABBB#
Trace |
AAAABBBB#
Trace |
AAAAABBBBB#
Trace |
|
|
For
this language, the measure of the "space complexity"
of this algorithm is rather straightforward. It is simply a direct
function of n, the length of the string. At the start,
n cells of the tape is required to store the input string.
As the function is computed no more space is ever required because
the algorithm erases the input as it computes the answer and
never writes any symbols anywhere on the tape.
The
measure of "time complexity" or the number of
steps required for a given input of size n is somewhat
more interesting. Recalling the algorithm by either visualizing
the actions of the algorithm in your mind or scrolling back to
the animation above will help us in describing one way in which
to arrive at the equation that describes the "time complexity"
of this algorithm.
Recall
that the algorithm proceeds by erasing one AB pair, then another,
and so on. It works from the outside of the input string and
"shrinks" the size of the string whenever it erases
a letter. At the start it erases the first A and traverses just
beyond the last B. This involves n + 1 moves to the right.
Then it erases the last B and moves just beyond the first remaining
A. This involves n moves to the left. It continues in
this fashion until no more letters are present. And, on each
traversal the length is reduced by one. Since there are n
items there are n traversals that must be made to erase
all of these items. Recall that n is equal to 2 times
j, the length of the block of A's or B's. Now if the traversals
stayed the same length throughout the algorithm, the number of
steps required to erase the letters would be 2jn + 1.
The one is added because the first traversal is n + 1
long. We will refer to this term as the maximum traversal, MT.
But
fewer steps are actually required because on each traversal the
length decreases by one. Consequently, we need a term that reflects
this decrease. Note that the length of the first pair of traversals
are n + 1 and n. It is only the remaining traversals
that can be used to decrease MT. The traversals can be thought
of as paired; j pairs in all. Since the first pair
is eliminated, there are j - 1 pairs that will contribute
to the decrease. You may remember from some algebra course in
your past that if we wish to sum k numbers (1 + 2 + 3
+... + k), then this sum is given by the formula: [k(k+1)]
/ 2. In the present case k is twice the number of remaining
paired traversals, namely 2(j-1). Thus, the term we require
is [2(j-1) x (2(j-1) +1)] / 2. Subtracting this
term from MT yields the number of moves made during the erasure
phase of the algorithm. But, the algorithm makes one additional
move to check that no letters remain and this move must be added
to yield the number of steps as a function of n. The complete
"ugly" but hopefully transparent form in which the
formula can be written is:
Steps(n) = [2jn
+ 1] - [ [2(j-1) x (2(j-1) +1)] / 2 ] + 1
Obviously,
this equation could be simplified. For example,
Steps(n) = (n/2
+ 1) (n + 1)
However,
on the next page is an algorithm that accepts strings of the
form AnBnCn. The first equation can be slightly modified to describe
this function for this algorithm, and we will use it for this
reason.
The
table below shows the number of steps required for this algorithm
as a function of n.
|
Number of Steps as a Function
of n
| j |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| n |
2 |
4 |
6 |
8 |
10 |
12 |
14 |
16 |
18 |
20 |
22 |
24 |
| Steps |
6 |
15 |
28 |
45 |
66 |
91 |
120 |
153 |
190 |
231 |
276 |
325 |
|
