 Chapter 17 shows how a 3tape DTM can simulate a NDTM.
Consider simulating the NDTM that semidecides the language of
strings that have at least two of the same letter
(Figure in slide 16 of Power Points Ch17b on D2L. Figure is not, to
my knowledge, in the book)
(Fig 17.??, section 17.3, 17.4, or 17.5).
Do the following:
 Draw the first six levels of the computation tree
for the string
cbc
. Each node will be a
configuration, written in parentheses.
Order children left to right by increasing state number.
 Near each node write, in square brackets,
the sequence of branch points that that node represents.
Number the branch points from left to right, starting at 1.
 Hint: The root node is (0, □cbc)
(0, □aba)
and it has one child
(1, cbc)
(1, aba)
.
 Hint: The sequence of branch points for the root is [1], and
for the root's child the sequence is [1,1]
 Hint: To simplify the NDTM simulation, the text gives
each node an equal number of children.
In your tree, however, nodes can have different number of
children.
 Hint: There are 14 nodes in the tree's first 6 levels.
 New Hint: Yes, even though the input string has just
3 characters, the computation tree has more than 4 levels
since, by assumption, ∀ and ¬a, etc, all include □.
 Please make sure that your answer is easily readable.
 Consider the encoded DTM <M1> below and do the following:
 Make reasonable assumptions about what alphabet symbols
are encoded and show the encoding of those symbols.
 Draw the machine it represents.
Use the alphabet symbols that you assumed above.
 Describe the language accepted by M1.
Use the alphabet symbols that you assumed above.
<M1> = (q000, a00, Y011, a00, R),
(q000, a01, q001, a11, R),
(q000, a10, N100, a10, R),
(q000, a11, q000, a11, R),
(q001, a00, N100, a00, R),
(q001, a01, q001, a01, R),
(q001, a10, q010, a11, L),
(q001, a11, q001, a11, R),
(q010, a00, q000, a00, R),
(q010, a01, q010, a01, L),
(q010, a10, N100, a10, R),
(q010, a11, q010, a11, L)

Consider the language L = {<M, w> : M
accepts w}.
Show two (encoded) strings
that are in the languages, where M is the TM M1 in the previous problem.
To represent the
encoded TM M1 from the previous problem in your answer,
you may simply use the name M1,
but for the string w, use the encoding of the alphabet symbols.
 Draw a diagram (similar to the Figure in Example 17.21 in section 17.6 page 404,
also slide 29 in PPT Ch17c on D2L)
that shows operation of a transformation machine T with the
following specification:
 Input to T: an encoded TM <M_{1}>
 Output from T: an encoded TM <M_{2}>
 Such that M_{2}(w) = M_{1}(ww)
 Thus, T must create a machine that duplicates its
input string and then runs M1
 You can use various standard
machines (eg a copy machine that transforms
w
into ww
)
as long as you precisely specify what that machine does.
 Note that the work of this assignment is drawing,
similar to fig 17.??, TM M_{2 }.
You can simply draw TM T as a black box.
 20.9
 For Exercise 20.9 make sure that you look at the Printing subroutine
P that is described in
Section 20.5.1 and in Exercise 8.