Mathematical Foundation of Computer Science

DHARM

222 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Î

Î

Î

Î

Î

Î a

a

b

Î

Î

Î

b

N΢²

Î

Step 4. Do the concatenation construction with the previous automaton N∈′′′ to the
newly constructed automaton N∈′′′′ (for regular expression r 4 = (a + b)*) so we obtain the final
NFA with ∈ moves N∈.
Since N∈′′′ will be,
Î

Î

a

b

Î

Î

Î

Î

Î

Nβ²

Now automata N∈′′′ will concatenate with N∈′′′′ that resulted N∈ which is shown in Fig. 9.6.

Î

Î

a

b

Î

Î

Î

Î

Î

Î

Î

Î

Î

Î

Î a

a

b

Î Î Î b Î Î

Î Nβ¢

Fig. 9.6 N∈.