DHARMREGULAR EXPRESSIONS 225(^0) D E
1
A
B
C
1
0
1
0
0
F
1
0, 1 0, 1
Fig. 9.7
Since automaton shown in Fig. 9.7 fulfills the deterministic requirement of the finite
automaton such that from every state there is one and only one exit on each symbol hence it is
a DFA.
Example 9.5. Construct a DFA for the regular expression 1 (1 + 1 0) + 1 0 ( 0 + 0 1).
Sol. Let M be an equivalent DFA for regular expression r = 1 (1 + 1 0) + 1 0 ( 0 + 0 1)
i.e., L(M) = L(r). Since, the regular expression r is formed by addition of regular expressions r 1
and r 2 where r 1 = 1 (1 + 1 0) and r 2 = 1 0 ( 0 + 0 1) i.e., r = r 1 + r 2 and their language is L(r 1 )
= {1 or 1 followed by any string formed over (1, 10)} or L(r 2 ) = {10 or 10 followed by any string
formed over (0, 01)}.
So, L(r) = L(r 1 ) ∪ L(r 2 )
Assume M 1 and M 2 are two DFA corresponding to the languages L(r 1 ) and L(r 2 ) hence,
L(M) = L(M 1 ) ∪ L(M 2 ).
(Construction of DFA M 1 )
Assume A is the start state of DFA then over symbol 1, M 1 reach to accepted state B.
Since, next to state B all strings of {1, 10} should be accepted. So, from state B over symbol 1 M 1
reaches to another accepted state C, otherwise the string 1 followed by 0 is accepted by adding
an repetetion arc from state C to state B over symbol 0. All repetition of symbol 1’s are ab-
sorbed at state C itself. Since, there is no possibility of exit arc over symbol 0 from state A as
well as state B hence these arcs terminates to state Ø. (Fig. 9.8)
B C
(^11)
0
1
A
F
00
Fig. 9.8. (M 1 ).
(Construction of DFA M 2 )
From starting state A string 10 is accepted (through P), so state Q will be accepted state.
Next to state Q all strings of {0, 01} should be accepted. So, from state Q an arc reaches to
another accepted state R over the symbol 0 and from R a returning arc over 1 reaches to
accepted state Q. An repetitions of symbols 0 are absorbed at state R itself. Transitions of 0