DHARM226 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
from A, 1 from P and 1 from Q must terminate to state Ø. Thus we get the automaton M 2.
(Fig. 9.9)
Q R(^00)
0
1
()M 2
A P
1
F
0
1
1
Fig. 9.9
The automaton M 1 and M 2 can be combined together so we obtain final automaton M
which is shown in Fig. 9.10.
B C
(^11)
0
1
A
F^1 Q R
1
0
0
0 1 0
Fig. 9.10M.
(For a single regular expression (regular language) there might exists more than one
DFA)
9.4 Finite Automata to Regular Expression........................................................................
(9.4.1 construction of DFA from regular expression)
Theorem 9.2. Let M be a DFA then there exists a regular expression r i.e., L(M) = L(r).
Proof. Theorem states that a finite automaton DFA can be equivalently expressed in some
form of regular expression. It means, that both DFA and regular expression concur on same
set of strings called regular language. The proof of the theorem illustrates how a regular ex-
pression can be constructed from a given DFA. Let M be a DFA that can be expressed as,
M = (Q, Σ, δ, q 1 , F) [where q 1 is the start state and F is the set of final states]
Assume set Q contains n states i.e., {q 1 , q 2 , ........... qn}. Now we introduce a new term
iRj
K, which contains set of strings. Assume, string x is derived from expression
iRj
K. Then,
expression iRjK is defined as,
iRj
K = {x ∈ Σ* / δ∧(q
i, x) = qj, i.e., ∀qm < qk (for i < ∀m < j) and
(qi and/or qj) ≥ qk, where qm is the intermediate state between qi and qj}