Mathematical Foundation of Computer Science

DHARM

220 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

l and δ∈ will be defined as,
δ∈(q, ∈) = {q 1 } or δ∈(q, ∈) = {p} and,
δ∈(p 1 , ∈) = {p} or δ∈(p 1 , ∈) = {q 1 }.
Hence, the path in automaton N∈ from starting state q to p follows either, through
l ∈-transition from q to p for automaton N∈, Or
l ∈-transition from q to q 1 in automaton N∈, followed by a path from q 1 to p 1 in N∈ 1
followed by ∈-transition from p 1 to p.
So, if x is the string labeled from q to p for automaton N∈ iff, x = x 1 .x 2 .x 3 .......xi (for
∀ i = 0 i.e., if i = 0 then x = ∈), for ∀ xi ∈ L(N∈ 1 ) hence,
L(N∈) = L(N∈ 1 ).
Hence, from the known automaton N∈ 1 that accepts the language L(r 1 ) we can construct
the automaton N∈ that accepts the language L(r 1 *). For N∈ the nature of accepting strings will
be,

1. ∈, or


2. finite repetition of the string of L(r 1 ),
   So, both these possibilities must be incorporated when we construct the N∈ such that,
   for 1, start state is connected to the final state by ∈-transition and for 2, the final state of
   automata N∈ 1 is connected to its start state through ∈-transition that will allow the one or
   more repetition of the strings of L(r 1 ). (Fig. 9.4)

L( )r 1

Î

q p

Î

Î

Î

q 1 p 1

NÎ 1

Fig. 9.4. (N∈).
Hence, we see that the theorem is true for regular expressions using single operator.
Through method of induction we can also show that theorem is true for regular expressions
having n operators. Therefore, we conclude that theorem is true for regular expressions form
over any number of operators. So, we constructed NFA with ∈-moves for all possible forms of
regular expressions, hence theorem verification is over.
Using the statement of the above theorem we can conclude followings,
l A regular expression converges to NFA with ∈-moves,
l Since we know that, NFA with ∈-moves converges to NFA (without ∈-moves) and
l Finally, NFA converges to DFA