Mathematical Foundation of Computer Science

DHARM

184 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

= k∪=

i

1 δ(,)pk a

= { r 1 , r 2 , r 3 , ............, rj}‡

Abstract view of the automata during scanning the string x = y a is shown below in

Fig. 7.20.

Þ

NFA q

............y............

N

NFA pp 12 / /....../pi

............y............

N

a

state

a

⇒

NFA rr 12 / /....../rj

............y............

N

a

state

Fig. 7.20

Example7.11. Fig. 7.21 shows a NFA N (similar to the automaton discussed in previous exam-

ple), then check its nature of acceptance over the string 101101.

q 0 q 2 q 3

1

q 1

0 1

0, 1 0, 1

N
Fig. 7.21
Sol. Above NFA N can be defined as,
N = ( {q 0 , q 1 , q 2 , q 3 }, {0, 1}, δ, q 0 , {q 3 });
where δ’s are shown in the following transition table (TT),

State

Input symbol

0

{q 0 ,q

q

1

3

}

}

F

F

{

q

q

q

q

0

1

2

3

1

{

{

{

{

q

q

q

q

0

2

3

3

}

}

}

}

‡ Case I, j = i, when all the state have single transition on each symbol of the set Σ then, † it

returns to exactly similar number of state that is equal to I or { r 1 , r 2 , r 3 , ............, ri}.

Case II, j = 0, when there is no transition arc over symbol a from state pk (∀k = 1 to i).

Case III, j < i or j > i, depending upon the nature of transition from state pk on input symbol a.

Above cases exists only because of dynamic nature of NFA.