Mathematical Foundation of Computer Science

DHARM

N-COM\CMS12-1.PM5

342 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Example 12.3. Construct the Turing machine for the language L = {ai bi ci | i ≥ 0}.
Sol. The construction of Turing machine M is similar to the previous example. Here the ma-
chine count the equal number of a’s followed by same number of b’s followed by same number
of c’s. By applying the similar logic we proceed as,

• Replace first a by X (count one a); reaches to last b; replace last b by c(counted symbols
  are 2); replaces last 2 c’s to B (blank) corresponding to the 2 symbols that are first a
  and last b.


• Repeat the previous step until the string of tape symbol X’s followed by B’s will found.
  a/ aabbb/ c /c /c
  ⇒ Xa/ abb/ /c /c BB
  ⇒ XXa/ b/ c BBBB
  ⇒ XXX/c /c BBBB ⇒ XXXBBBBBB
  In the similar fashion we define the transition functions and thus we obtain the state
  diagram of the Turing machine which is shown in Fig. 12.11.
  State Diagram

q 0 q 1

q 8

( , X, R)a (, ,R)bb q

2

(B, B, R)

(, ,R)aa

(X, X, R)

(, ,R)bb

(, ,L)cc q

3

(, ,R)bc q

4

(, ,R)cc

q 5

(B, B, L)

q 7 q 6

( , B, L)c ( , B, L)c

(, ,L)cc

(, ,L)bb

(, ,L)aa

Fig. 12.11

12.4 General Problems of a Turing Machine.........................................................................

Now we discuss the general problems of a turing machine that is if, α q β * α p ξ β where α,

β ∈Γ* and q and p ∈ Q and ξ ∈ Σ; then how a machine handle this situation. The fact of the

problem is, pushing of an extra symbol between strings ααααα and βββββ (in finite steps). In

other words how to create a free space between the strings α and β so that an extra symbol will

place them.

a b a a ......... b B ....

q

a b

a b x a ......... b B

q

a b

a

(a)(b)

Fig. 12.12