UnisaAssignHelp
COS3701
Assignment 3
Unique Number:
830430
, UnisaAssignHelp
Question 1
Problem 6 (ii) on page 454:
Design a turing machine to accept the language anb2n
The TM in Figure 1 solves this problem.
From the START state an a is read and an A is printed on the tape. In state 1 the TM loops, moving the tape
head right, for all the as read until the first b is read.
If the first b is read a B is printed on the tape, the tape head moves right and we are at state 2. Another b
is read and the next B is printed on the tape, the tape head moves left, we arrive at state 3.
In state 3 we loop to the left reading first Bs and then as until we encounter an A which takes us to state 4.
In state 4 we read an a if all the as read have not yet been converted to As else we read a B. If we read an
a in state 4 the TM prints an A on the tape and the tape head moves right.
We are now in state 1 and the described cycle state 1 – state 2 – state 3 – state 4 is repeated until a B is
read in state 4.
If a B is read in state 4 we move to state 5. In state 5 we loop to the right through all the characters on
the remainder of the tape. If all these characters are Bs and we finally read ∆ then we move to the HALT
state.
Note, in short we compare the number of as to the number of bs by converting two bs to Bs for each a
converted to an A.
COS3701
Assignment 3
Unique Number:
830430
, UnisaAssignHelp
Question 1
Problem 6 (ii) on page 454:
Design a turing machine to accept the language anb2n
The TM in Figure 1 solves this problem.
From the START state an a is read and an A is printed on the tape. In state 1 the TM loops, moving the tape
head right, for all the as read until the first b is read.
If the first b is read a B is printed on the tape, the tape head moves right and we are at state 2. Another b
is read and the next B is printed on the tape, the tape head moves left, we arrive at state 3.
In state 3 we loop to the left reading first Bs and then as until we encounter an A which takes us to state 4.
In state 4 we read an a if all the as read have not yet been converted to As else we read a B. If we read an
a in state 4 the TM prints an A on the tape and the tape head moves right.
We are now in state 1 and the described cycle state 1 – state 2 – state 3 – state 4 is repeated until a B is
read in state 4.
If a B is read in state 4 we move to state 5. In state 5 we loop to the right through all the characters on
the remainder of the tape. If all these characters are Bs and we finally read ∆ then we move to the HALT
state.
Note, in short we compare the number of as to the number of bs by converting two bs to Bs for each a
converted to an A.
