Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 217

(Provided that N∈ has only one final state and there is no outgoing arc from the final
state)
Proof. We shall prove the theorem in this way that if r be a regular expression and its lan-
guage is L(r) then its all possible strings we can construct an equivalent NFA with ∈-moves
which accepts same set of strings. The proof of the theorem is preceded by method of induction.
First we construct the N∈ for the basis regular expressions i.e. regular expressions without
any operator.
l If r = ai then L(r) = {ai/ai ∈ Σ for ∀ i = 1 to n}, then equivalent automaton N∈ that
accepts L(r) will be,

q p

ai

(By assuming that automaton N∈ initially is in state q and after reading symbol ai it

reaches to state p and then stop)

l If r = ∈∈∈∈∈ then L(r) = {∈} then automaton N∈ that accepts ∈ or null string will be,

Or,

q

q Î p

(Initially N∈ is in state q and after reading ∈ automaton think a meaningless symbol so
it remains in state q alternatively its state changes to p and then stop)
l If r = ΦΦΦΦΦ then L(r) = Φ. The automaton N∈ that accepts language Φ will be,

q p

(Initially N∈ is in state q and there is no way (set of language consists nothing) to reach
to final state p).
Thus we have seen that we can construct the equivalent NFA with ∈ moves for the basis
regular expressions. Further, we will see that N∈ can also be constructed for the composite of
regular expressions, which are form over operators union, concatenation and Kleeny closure.
Assume that regular expression r is form using these n operators. By Induction hypothesis we
assume that theorem is true if r has ≤ (n – 1) operators (for n ≥ 1). Let r has exactly n operators
then construct an equivalent N∈ for regular expression r. Here we will show that theorem is
true for composite of two regular expressions obtained using union, concatenation, and closure
operations.
Let r 1 and r 2 be two regular expressions then following are the possible regular expres-
sions,

1. if r = (r 1 + r 2 ) then its language is L(r) = L(r 1 ) ∈ L(r 2 )


2. if r = (r 1. r 2 ) then its language is L(r) = L(r 1 ). L(r 2 )


3. if r = r 1 then its language is L(r) = L(r 1 )
   Assume that corresponding to regular expression r 1 N∈ 1 be the equivalent automaton
   accepting L(r 1 ) then it looks like as,