Problem Solving in Automata, Languages, and Complexity

4.1 One-Tape Turing Machines 163

B/B,

-cl

L h

du, R

b/b, R

Figure 4.2: The transition diagram of the DTM Ml.

state p does nothing but introduces an infinite loop. For simplicity, we may

eliminate the state p and present S in the following form:

S 41AL

41 41, a, L 41AL Q2AR

!I2 4243 43AR

!I3 43, b, R ov

The blank entries in the above table (s(s, a), 6(s, b), h(q2,B) and b(q3, a))

indicate that if the machine enters such a configuration (i.e., (s, ~gy), (s, zby),

(q2, zgy) or (43, zay) for some X, y E I’*), it will enter an infinite loop and does

not accept the input. In other words, we will allow the transition function S

to be left undefined on some input (q, a). If the value of S( q, a) is undefined,

then it means that the machine will move into an infinite loop.

Similar to DFA’s and PDA’s, a one-tape DTM can also be represented by

a transition diagram. Each vertex in a transition diagram represents a state.

Each edge‘in a transition diagram has a label of the form “a/b, R” or “a/b, L”.

An edge from state q to state p with label “a/b, R” (or, “a/b, L”) represents

the instruction S(q, a) = (p, b, R) (or, respectively, 6(q, a) = (p, b, L)). For

example, the DTM Ml of Example 4.1 can be represented by the transition

diagram of Figure 4.2.

For any DTM M, we let L(M) = {X E C* 1 M accepts z}. A language

L is called Turing-acceptable if L = L(M) for some DTM M. In the above

example, it is not hard to see that L(M1) = {a”bn 1 m 2 0, n 2 l} = a* bb*.

It is a special case of the following theorem.

Theorem 4.2 Every regular language is Turing-acceptable.

ProoJ Let L be accepted by a DFA M = (Q, C,S, qo, F). We construct a