Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

INTRODUCTION TO TURNING MACHINE 339

•δ(q 1 , B) = (q 2 , B, L) // find the last b

•δ(q 2 , b) = (q 3 , B, L) // last b is replaced by B and move left

•δ(q 3 , b) = (q 3 , b, L) and δ(q 3 , a) = (q 3 , a, L) // skip all a’s and b’s and move left and

reaches to X

•δ(q 3 , X) = (q 0 , X, R) // X remains X and move right

•δ(q 0 , B) = (q 4 , B, R) // B remains B and halt.

So, F = {q 4 } or halting state

State Diagram

q 0 q 1

q 4

( , X, R)a (B, B, L) q

2

( , B, L)b q

3

(, ,L)bb

(, ,L)aa

(, ,R)aa

(, ,R)bb

(B, B, R) (X, X, R)

Fig. 12.8
Note, the definitions of δ defined above are the only possibilities for the acceptance of the
strings of L. For rest of the moves (not defined above) machine will crashes or disappear.

ID’s View

(Start) q 0 a a b b X q 1 a b b X a q 1 b b X a q 1 b b X a b q 1 b X a b b q 1 B X a b q 2
b X a q 3 b X q 3 a b q 3 X a b X q 0 a b X X q 1 b X X b q 1 B X X q 2 b X q 3 X
X X q 0 B X X B q 4 B (Halt)

12.3 Language of a Turing Machine.......................................................................................

Let M be a Turing machine defined as, M = (Q, Σ, Γ, B, q 0 , δ, F) then language of M be L(M),
where
L(M) = {x ∈ Σ | q 0 x α 1 p α 2 and p ∈ F} where α 1 , α 2 ∈ Γ*
It means that the string x is in the language of machine if from starting state q 0 machine
M reaches to the state p (final state) after scanning the complete string x (whatever the tape
symbols it left α 1 and α 2 )
The language of the Turing machine is the recursive enumerable language. The accept-
ance that is commonly used for turing machines is the acceptance by halting. It means turing
machine halts if there is no move define further in that instance of problem state. Alterna-
tively we can always assume that a turing machine always halts when it is in an accepting
state.
In fact a class of languages whose turing machine halts, regardless of whether or not it
reaches an accepting state are called recursive languages. The other class of languages con-
sists of there recursive enumerable languages that are not accepted by any turing machine
with the guarantee of halting. These languages are accepted in an in convenient way.

Example 12.1. Construct the TM for the language L = {ai bi | i ≥ 1}.
Sol. We can construct the TM for L by applying different logic used in the previous example,
i.e., for counting equal number of a’s followed by b’s we go through following steps: