Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 221

Therefore, DFA converges to Regular Expression. There relationship is pictured in Fig. 9.5.

DFA NFA

Regular

Expressions

NFA with

Î-moves

Fig. 9.5

Example 9.3. Construct the NFA with ∈-moves for regular expression

(a + b). a. b*. (a + b)*.

Sol. Assume r = (a + b). a. b*. (a + b)*, where r is formed by the concatenation of four regular

expressions i.e., r = r 1. r 2. r 3. r 4 where r 1 = (a + b); r 2 = a; r 3 = b* and r 4 = (a + b)*. Now we

construct the NFA with ∈ moves for r using theorem 9.1 in the following steps,

Step 1. Construction of the automaton for r 1 = (a + b) is the addition of two automatons

accepting the union of language {a} and {b} i.e., (Let it be N∈′)

a

b

Î

Î Î

Î

N΢

Step 2. Now regular expression r 1 is concatenated with regular expression r 2 = a so,

automaton N∈′′ will be constructed, i.e., L(N∈′′) = L(N∈′). L(a), thus N∈′′ will be obtain as,

a

b

Î

Î Î

Î

Nβ

Î a

Step 3. Next, regular expression r 1. r 2 is concatenated with r 3 = b*, so again concatenation
construction of L(N∈′′) with automaton that accept L(r 3 ). Thus we obtain N∈′′′.