Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

338 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

a b a b

q

a bb

p

X

()a ()b

Fig. 12.6

As usual a state is represented by a circle, A start state is represented by a circle marked

with an arrow, and the final state (halting state) is represented by the double circle.

Alternatively state diagram of Fig. 12.7

q 0 q 1

(, ,R)aa

Fig. 12.7

shows that from the starting state q 0 machine reads the symbol a and left the same symbol a

(over write a by a) and move to right and reaches to state q 1 and halted (shown by double

circled).

Let us consider an example and construct the Turing machine for the language

L = {ai bi | i ≥ 0}. We see that language L contains all the strings of equal number of a’s

followed by equal number of b’s like,

L = {ab, aabb, aaabbb, .................. and ∈}

So, we construct the Turing machine that accepts the strings, which are in set L.

Logic

The logic for scanning the accepted nature strings is depend upon the counting of the number

of a’s and b’s with followings steps: (assume string is ‘aaabbb’)

• Read the first symbol a, converted to X, move right and find the equivalent b at the
  end of the string (before the blank symbol B) and converted to B.
  a a a b b b B B ⇒ X a a b b B B B


• Move back and reach to the next starting symbol a and repeat the previous step like
  as,
  X a a b b B B B ⇒ X X a b B B B B
  and X X a b B B B B ⇒ X X X B B B B B (a string of only X and blanks B)


• The string of equal number of a’s followed by b’s certainly returns the string shown
  above that is last X followed by B and this may be taken as the halting condition of
  the machine.

Transition functions (δ)

Let machine M = (Q, Σ, Γ, B, q 0 , δ, F) where q 0 is the starting state, set Q = {q 0 , q 1 , q 2 , q 3 , q 4 },
Σ = {a, b}, Γ = {a, b, X, B} (because Σ ⊂ Γ) and δ are defined as follows:
•δ(q 0 , a) = (q 1 , X, R) // first a is replaced by X
•δ(q 1 , a) = (q 1 , a, R) and δ(q 1 , b) = (q 1 , b, R) // skip all a’s and b’s and move right so it
reaches to symbol B