COM S 331: Theory of Computing, Summer 2021
Homework Assignment 6
Due at 11:59PM, Wednesday, June 23, on Gradescope.
Problem 22 (35 points). Give the state diagram of a Turing machine that recognizes the lan-
guage L = {aibjci+j | i, j ∈ N}.
Solution There are many different designs, depending on how you want to approach this problem.
This is just one way to build the Turing machine for this language. Assume all missing transitions
lead to the reject state.
The idea for this machine is to delete the leftmost ’a’ then rightmost ’c’, repeat until all ’a’ are
deleted, then delete the leftmost ’b’ and rightmost ’c’, repeat until all ’b’ are deleted, accept if there
are nothing left on the tape.
States q0a-q3a form the loop to delete the leftmost ’a’ (q0a), move head to the end of the input
(q1a), delete the rightmost ’c’ (q2a), move head back to the beginning of the input (q3a). If at
state q0a the leftmost symbol of the input is a ’b’, then it will delete the leftmost ’b’ instead and
1
move to q1b.
States q0b-q3b form the loop to delete the leftmost ’b’ (q0b), move head to the end of the input
(q1b), delete the rightmost ’c’ (q2b), move head back to the beginning of the input (q3b).
There is a separate loop for deleting ’a’ and ’b’ to make sure that all the ’a’ comes before ’b’, else
it will stop at q1b. If there are ’a’ or ’b’ after ’c’, it stops at q2a or q2b because it is expecting to
delete the rightmost ’c’ but there is another symbol instead. If there are more ’c’ than ’a’ and ’b’,
the machine will stop at q0a or q0b. If there are less ’c’ than ’a’ and ’b’, then it will stop at q2a or
q2b because there is no ’c’ to be deleted.
Problem 23 (35 points). Give the state diagram of a Turing machine that recognizes the lan-
guage L = {anb2n | n ∈ N}.
Solution Assume all missing transitions lead to the reject state.
The idea for this machine is to delete the leftmost ’a’ then 2 of the rightmost ’b’, repeat until all
’a’ are deleted, accept if there are nothing left on the tape.
This works pretty similar to the previous questions, instead of always deleting 1 rightmost symbol,
it deletes 2 of the rightmost symbols. The rest of the concept is the same.
Problem 24 (30 points). Consider a variant of Turing machine called 2-cell Turing machine
which has a finite set of states, a semi-infinite left-ended tape (just as a standard Turing machine),
a read/write tape head that has access to 2 tape cells, i.e., in a single step, the head can simulta-
neously read the tape cell under it and the tape cell to the right of it, and can write to those two
cells. Show how you can simulate these 2-cell Turing machines with standard Turing machines.
2
Solution Let the M = (Q,Σ,Γ, δ, q0, qaccept, qreject) be an arbitrary 2-cell Turing machine. We can
construct a standard Turing machine M ′ = (Q′,Σ,Γ, δ′, q0, qaccept, qreject) such that L(M) = L(M
′)
and Q′ = Q ∪ {qa | ∀q ∈ Q and a ∈ Σ} ∪ {qaD | ∀q ∈ Q, a ∈ Σ and D ∈ {L,R}}.
Since the standard TM can only read/write one cell at a time, to simulate a 2-cell TM, a standard
TM has to take 3 transitions for every transition of the 2-cell TM:
(1) “record” the symbol in current cell and move right to read the symbol of the next cell,
(2) write this cell according to the transition of 2-cell TM, “record” the symbol that needs to be
written in the previous cell and also the new state it will transition to and move left,
(3) write this cell, update the state, and move according to the transition of 2-cell TM.
Thus both current and the next cells are read and written, and the state of TM is updated.
In a more formal language, let’s define a transition in the 2-cell TM as δ(q, {a, b}) = (p, {c, d}, D)
where q, p ∈ Q, a is the content in current cell and b is the content in the cell right of it, c is the
symbol to be written on current cell and d to be written on the next cell, and D ∈ {L,R}.
For every such transition, the standard TM will have
δ′(q, a) = (qa, a, R) for step (1),
δ′(qa, b) = (pcD, d, L) for step (2), and
δ′(pcD, a) = (p, c,D) for step (3).
Here we used the naming convention of the states to “record” information we needed to carry
forward. If the TM is in some state q reading symbol a, then it should move right and transition
to state qa. If the TM is in some state qa and is currently reading a b, then it should transition
according to the transition of 2cell TM (δ(q, {a, b}) = (p, {c, d}, D)) to state pcD, write d and move
left. If the TM is in some state qaD, then it should write the current cell as a, transition to state q,
and move D.
3