Mathematical Foundation of Computer Science

DHARM

REGULAR AND NONREGULAR LANGUAGES 263

Lemma 10.2.
Let r is a regular expression and it generates the language L. Assume regular expression r can
be formed by concatenation of regular expressions r 1 , r 2 , r 3 ,............ rn , where ri, (∀ i ≥ 1) may
be formed by addition of regular expressions or kleeny closure of it.
r = r 1. r 2. r 3 ......rn. (because concatenations of regular expressions are regular expression)
If we concatenate the above regular expressions in reverse order we get again a regular
expression.
rREV = rn. rn–1......r 3. r 2. r 1
Regular expression rREV generates the language that certainly contains the strings that
are reverse of the strings of L.
For example r = a 1. a 2. a 3 ......an and it expresses the language L = a 1 a 2 a 3 ......an then
reverse of L is an......a 3 a 2 a 1. That is generated from the concatenation of the regular expressions
in reverse order
i.e., rREV = an......a 3. a 2. a 1
Since, rREV is a regular expression. Hence its language is also regular.
FACT
If L is the language accepted by some DFA then we can construct the DFA (one/more) that
accepts reverse of all the strings of L.
Proof. Let DFA M = (Q, Σ, δ, q 0 , F) is represented by equivalent regular expression r where
L = L(r). Let reverse of L is LR where LR = (L)R = (L(r))R = L(rR) says reverse of L is expressed
by a regular expression rR. Hence, there exist some DFA equivalent to regular expression rR.
Now, we construct the DFA MR with following consideratons, i.e.,
l Starting state of M becomes the final state of MR.
l Final state of M will be the starting state of MR.
l If M has more than one final state then number of DFA MR are more (number of MR
will be depend upon the number of final states)

1. Select any one final state (of M) that will be the starting state of MR1, remaining
   final states becomes non final states of MR1.


2. Pick next final state (of M) that will be the starting state of MR2 and remaining
   final states becomes non final states of MR2.


3. Repeat step 2 until all final states becomes starting state of MR1, MR2,......MRk
   where k is the number of final states in M. So there are K possible DFA (MR) that
   accept reverse of language L.
   l Reverse direction of all the transition arcs.
   For example Fig. 10.9 shows a DFA M accepts language L, where L is the language
   denoted by regular expression 0 . 1. 1 + 0. 1. 1. 0. (1 + 0)*

A B

0 1

(^10) C
1, 0
Fig. 10.9