Mathematical Foundation of Computer Science

(Chris Devlin) #1
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∈′′′.

Free download pdf