DHARM
N-COM\CMS12-1.PM5340 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE- replace starting symbol a by X, then reaches to the first b and replace by Y
- move back and find next starting symbol a and repeat the previous step
- until found X followed by Y
Lets input string is ‘aabb’. Then applying above steps it will converted on ‘XXYY’
The machine will terminate certainly with the condition that last X is followed by Y.
Let q 0 be the starting state, Q = {q 0 , q 1 , q 2 , q 3 , q 4 }, Σ = {a, b}, Γ = {a, b, X, Y, B} and halting
state F = {q 4 } then Transition function (∂) are follows:
•δ(q 0 , a) = (q 1 , X, R)
•δ(q 1 , a) = (q 1 , a, R) and δ(q 1 , Y) = (q 1 , Y, R) // skip all a’s and Y’s and move right and
reaches to first b (corresponds to first a)
•δ(q 1 , b) = (q 2 , Y, L) // replace b by Y and move left
•δ(q 2 , a) = (q 2 , a, L) and δ(q 2 , Y) = (q 2 , Y, L) // skip all a’s and Y’s and move left and
reaches to X
•δ(q 2 , X) = (q 0 , X, R) // X will remain X and move right
•δ(q 0 , Y) = (q 3 , Y, R) // if no more symbol left then machine certainly reaches to Y It
remains Y and move to right
•δ(q 3 , Y) = (q 3 , Y, R) // skip all Y’s and reaches to blank
•δ(q 3 , B) = (q 4 , B, R) // blank remains blank and halt
State Diagram
q 0 q 1q 4( , X, R)a ( , Y, L)b q
2(Y, Y, R)q 3(, ,R)aa
(Y, Y, R)(B, B, R)(X, X, R)(Y, Y, R)(, ,L)aa(Y, Y, L)Fig. 12.9ID View’s (Let’s trace the moves of TM for the string ‘aabb’)
(Start) q 0 a a b b X q 1 a b b X a q 1 b b X q 2 a Y b q 2 X a Y b X q 0 a Y b
X X q 1 Y b X X Y q 1 b X X q 2 Y Y X q 2 X Y Y X X q 0 Y Y X X Y q 3 Y
X X Y Y q 3 B X X Y Y B q 4 B (Halt)Example 12.2. Construct the Turing machine for the Context Sensitive Language
L = {ai bi ai | i ≥ 0}.
Sol. Here the language L consist of strings of equal number of a’s followed by equal number of
b’s followed by equal number of a’s resembling {aba, aabbaa, aaabbbaaa....}. So to check up
this condition we apply following logic: