Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 185

Then we check the behavior of N over the string 101101, from the starting state q 0.

I. $δ(q 0 , 101101) = $δ(δ(q 0 , 1), 01101);

[from TT check transition response of state q 0 on symbol 1]

= δ$(q 0 , 01101); [∴δ (q 0 , 1) = {q 0 }]

II. (^) δ$(q 0 , 01101) = $δ(δ (q 0 , 0), 1101);
= δ$({q 0 , q 1 }, 1101); [∴δ (q 0 , 0) = {q 0 , q 1 }]
III. (^) δ$({q 0 , q 1 }, 1101} = $δ(q 0 , 1101) ∪ (^) δ$(q 1 , 1101); [check each one separately]
IV(A1). $δ^(q 0 , 1101) = δ$(δ (q 0 , 1), 101);
= δ$ (q 0 , 101} [∴δ(q 0 , 1) = q 0 ]
IV(A2). (^) δ$(q 0 , 101) = $δ(δ(q 0 , 1), 01);
= δ^(q 0 , 01) [∴δ(q 0 , 1) = q 0 ]
IV(A3). δ$(q 0 , 01) = $δ(δ(q 0 , 0), 1);
= δ$({q 0 , q 1 }, 1); [∴δ(q 0 , 0) = {q 0 , q 1 }]
IV(A4). (^) δ$({q 0 , q 1 }, 1) = δ$({q 0 , q 1 }, 1.∈);
[in case of δ$ when symbol is alone, to make it string , it
will multiply with the null string (∈)]
= δ$(q 0 , 1.∈) ∪ (^) δ$(q 1 , 1.∈);
= δ$(δ(q 0 , 1), ∈) ∪ (^) δ$(δ(q 1 , 1), ∈);
= δ$(q 0 , ∈) ∪ (^) δ$(q 2 , ∈); [see transitions of state in TT]
= {q 0 } ∪ {q 2 }; [by applying Ist the property of $δ
= {q 0 , q 2 }; i.e., δ$(q 0 , ∈) = q 0 and δ$(q 2 , ∈) = q 2 ]
So we find none state is an acceptable state.
IV(B1). δ$(q 1 , 1101) = $δ(δ(q 1 , 1),101);
= δ$(q 2 , 101); [from the TT δ(q 1 , 1) = q 2 ]
IV(B2). (^) δ$(q 2 , 101) = $δ(δ(q 2 , 1), 01};
= δ$(q 3 , 01); [from the TT δ(q 2 , 1) = q 3 ]
IV(B3). (^) δ$(q 3 , 01) = δ$(δ(q 3 , 0), 1);
= δ$(q 3 , 1); [from TT δ(q 3 , 1) = q 3 ]
IV(B4). $δ(q 3 , 1 = $δ(q 3 , 1.∈); [see IV(A) explanation]
= δ$(δ (q 3 , 1), ∈);
= δ$(q 3 , ∈); [from TT δ(q 3 , 1) = q 3 ]
= {q 3 }; An acceptable state
Hence, NFA N will move over the string 101101 according to following paths,
1 011 0 1
q 0 q 0
01
0
11 01
q 0 q 0 q 0 q 0 q 0
q 1 q 2
q 1 q 2 q 3 q 3 q 3