Problem Solving in Automata, Languages, and Complexity

4.1 One-Tape Turing Machines

Exercises 4.1

165

Trace DTM A&r of Example 4.1 and show the computation of Ml on

inputs aabba and bbbab.

Consider the DTM Mz = (Q,V’,b) with& = {m,q2}, C = -b,b),

r = {a, b,B}, and

?JctJq&

(a) Trace M2 on inputs aaab, abaa and aaaa.

(b) What is L(M2)?

3. Consider the DTM M3 = (Q, C, I’, 6, s), with Q = {s, ql, q2, q3,q4, qs},

C = {a, b}, I’ = {a, b, B}, and

s S !I1 42 43 q4 45

a b

Ql4J q3, a, R 43, a, R q31 a, R h,@

alAL (74, b, R !l4J a, R q4, h R h,B,R

B QlAL (221 B, R 45, B, L 457 B, L q5A L

(a) Trace M3 on inputs aaabba and bbbaba.

(b) What is the function computed by Ma?

4. Consider the DTM M4 = (Q, C, I’,S, s), in which Q, C and I? are the

same as those of M3, and S is the same as S of MS except for

s a b B q5 45,aJ h,B,R ’

What is L(M4)?

5. Show that every regular language is Turing-decidable.

Assume that L C {O,l}* is Turing-decidable. Show that the language

{o,1)* - L is al; Turing-decidable. That is, for a given DTM M that

computes the characteristic function XL of L, describe in detail how to

modify M to get a new DTM M’ such that M’ computes the character-

istic function of (0, l}’ - L. Can you do the same for Turing-acceptable

languages?