Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 223

9.3.2 Construction of DFA from Regular Expression................................................

Any regular expression can be expressed by an equivalent finite automaton. Since theorem 9.1
suggests the construction of NFA with ∈-moves from regular expression. NFA with ∈-moves is
an extension of NFA hence NFA is constructed from them. Since, NFA is an ease of DFA
therefore from regular expression we can construct an equivalent DFA. So, this process of
construction such that, from regular expression to NFA with ∈-moves, from NFA with ∈-
moves to NFA, and then from NFA to a DFA is lengthy and tedious. To over comes this difficulty
we can alternatively constructed a DFA from known regular expression.

Example 9.4. Consider a regular expression r = (0 0 + 0 0 1).1 then construct a DFA accepts
the language L(r).
Sol. Concentrate on regular expression r = (0 0 + 0 0 1). 1 we will find that its language
L(r) can be subdivided like as,

L( )r

{1}[when closure generates ]Î

Any string formed over {00, 001}followed by 1

Assume A be the staring state of DFA, so from state A on symbol 1 automaton reaches to

accepting state B and on symbol 0 it reaches to a new state C.

A

B

C

1

0

For the acceptance of the string 001 we extend the state diagram as follows :

After state C return symbol is 0, therefore, from state C automaton reaches to the final

state E (return symbols on state E is 001) as shown below :

C D E

0

0 00 001

1

Thus, automaton look like,

(^0) D E
1
A
B
C
1
0