178 TURING MACHINES
(c) {umbnck 1 m > n > k > 0).
(d) {cPPc~+~ I;,u$ 07.
(e) {W E {a, b)* 1 Sita > #b(w)}, where #a(~) denotes the number
of occurrences of letter a in string w.
(f) {un1bun2b-bunk 1 ni = nj for some 1 < - i < j < - !C}.
4. Construct DTM’s to compute the following functions:
( ) a
(b)
( > C
(4
( > e
( f 1
f(m,n) = max{m, n} over natural numbers m, n.
f(q, n2,... , nk) = max{nl,... , nk} over natural numbers nl,.. .,
nk, where /C is a fixed positive integer.
insert”(xl,... , xk, y, i) = inser$(xl,... , xk, y), where xl,... , xk
and y are strings in (0, 1)” and i is a natural number represented
bY 1
i.
mult (n, m) = nm on natural numbers n, m > - 0.
quot(n,m) = I%] on natural numbers n > - 0 and m > - 1.
Zg(n) = [log:, nl on natural number n.
5. For any given DTM M, construct a new DTM W such that W accepts
exactly the same set of strings as that of U (i.e., L(M) = L(W)) but
when W halts its tape is always empty (i.e., the final configuration is
always (h, BE)).
6. Consider the regular language L = {On110n21 l JOnk I k > 5,
f-ho-, nk >_ 0, nj z nj+l (mod 5) where j = (k mod 5) + 1). -
(a) Find a read-only DTM M accepting L. [Hint: iW make two passes
over the input. In the first pass, it checks that Ic > 5 and finds
j= (k mod 5) + 1. In the second pass, it checks that nj =
nj+l (mod 5)*](b) Find all possible crossing sequences of ALJ on any input.
(c) For any two crossing sequences Sr , S2 of MI and for any symbol
a E (0, 1, B}, determine whether S1 $ S2. Based on this relation
between crossing sequences, construct an NFA iW’ that accepts L.
(d) Can you find an NFA with asmaller state set than iW’ that accepts
L?* 7. In the proof of Theorem 4.10, we observe that if the DTM 1M visits,
during its computation on input x, some blank cells to the right of
the input, then the NFA W needs to move, after reading all input
symbols, to other states by E-moves to decide whether it accepts the
input. Show that this is not necessary. That is, we can eliminate all
E-moves in S’ and change the set F of the final states to include all
crossing sequences S which contain (h, R) as the last pair such that
B B B