CSE322

Regular Expressions and

their Identities
Lecture #6
Regular Expressions
• The language accepted by finite automata can be easily
described by simple expressions called Regular Expressions. It
is the most effective way to represent any language.
• The languages accepted by some regular expression are
referred to as Regular languages.
• A regular expression can also be described as a sequence of
pattern that defines a string.
• Regular expressions are used to match character
combinations in strings. String searching algorithm used this
pattern to find the operations on a string.
Regular Expression
Phi- Empty Set; Epsilon- Null String: String is there but its null
• In a regular expression, x* means zero or
more occurrence of x. It can generate {e, x, xx,
xxx, xxxx, .....}
• In a regular expression, x+ means one or more
occurrence of x. It can generate {x, xx, xxx,
xxxx, .....}
Regular Expressions
We give a formal recursive definition of regular expressions over ∑
as follows:
1. Any terminal symbol (i.e. an element of ∑), Λ and ∅ are regular
expressions. When we view a in ∑ as a regular expression, we
denote it by a.
2. The union of two regular expressions R1and R2 , written as R 1 +
R2, is also a regular expression.
3. The concatenation of two regular expressions R1and R2, written as
R1 R2, is also a regular expression.
4. The iteration (or closure) of a regular expression R written as R*, is
also a regular expression.
5.If R is a regular expression, then (R) is also a regular expression.
6. The regular expressions over∑ are precisely those obtained
recursively by the application of the rules 1-5 once or several times
Definitions
Any set represented by a regular expression is
called a regular set.
If for example, a, b ε ∑. Then
(i) a denotes the set {a},

(ii) a + b denotes {a, b},

(iii) ab denotes {ab},

(iv) a* denotes the set {lambda, a, aa. aaa, ... } and

(v) (a + b)* denotes {a, b}*. The set represented by R is denoted by L(R),
Questions

Describe the following sets by regular expressions:

(a) {101}
(b) {abba}
(c) {01,10}
(d) {Λ ,ab}
(e) {abb,a, b, bba}
(f){Λ , 0, 00, 000.... }
(g) {1, 11, 111 ... }
Solution
(a) Now. {1}. {O} are represented by 1 and O. respectively. 101 is obtained
by concatenating 1,0 and 1 So. {10 I} is represented by 1*0*1.

(b) abba represents {abba}.

(c) As {01, 10} is the union of {01} and {10}, we have {01, 10}
represented by 01 + 10

(d) The set {Λ , ab} is represented by Λ + ab

(e) The set {abb, a, b, bba} is represented by abb + a + b + bba.

f) As {Λ , 0, 00, 000, ... } is simply {O}*. it is represented by 0*

(g) Any element in {1, 11, 111, ... } can be obtained by concatenating
1 and any element of {1}*. Hence 1(1)* represents {1, 11, 111, ... }
Example 1:
Write the regular expression for the language accepting all combinations of
a's, over the set ∑ = {a}
Example 1:
Write the regular expression for the language accepting all combinations of
a's, over the set ∑ = {a}
Solution:
All combinations of a's means a may be zero, single, double and so on. If a is
appearing zero times, that means a null string. That is we expect the set of
{ε, a, aa, aaa, ....}. So we give a regular expression for this as:
R = a*
That is Kleen closure of a.
Example 2:
• Write the regular expression for the language accepting all combinations
of a's except the null string, over the set ∑ = {a}
Example 2:
• Write the regular expression for the language accepting all combinations
of a's except the null string, over the set ∑ = {a}
• Solution:
The regular expression has to be built for the language
L = {a, aa, aaa, ....}
This set indicates that there is no null string. So we can denote regular
expression as:
R = a+
Example 3:
Write the regular expression for the language accepting all the
string containing any number of a's and b's.
Example 3:
Write the regular expression for the language accepting all the
string containing any number of a's and b's.

Solution:
The regular expression will be:
r.e. = (a + b)*
This will give the set as L = {ε, a, aa, b, bb, ab, ba, aba, bab, .....}, any
combination of a and b.
The (a + b)* shows any combination with a and b even a null string.
Example 4
• Write the regular expression for the language accepting all
the string which are starting with 1 and ending with 0, over
∑ = {0, 1}.
Example 4
• Write the regular expression for the language accepting all
the string which are starting with 1 and ending with 0, over
∑ = {0, 1}.
Solution:
In a regular expression, the first symbol should be 1, and the last symbol
should be 0. The r.e. is as follows:
R = 1 (0+1)* 0
Example 5
• Write the regular expression for the language
starting and ending with a and having any having any
combination of b's in between.
Example 5
• Write the regular expression for the language
starting and ending with a and having any having any
combination of b's in between.
• Solution:
The regular expression will be:
R = a b* b
Example 6
• Write the regular expression for the language
starting with a but not having consecutive b's.
Example 6
• Write the regular expression for the language
starting with a but not having consecutive b's.
Solution:
The regular expression has to be built for the
language:
L = {a, aba, aab, aba, aaa, abab, .....}
The regular expression for the above language is:
R = {a + ab}*
Example 7
Write the regular expression for the language accepting all the
string in which any number of a's is followed by any number
of b's is followed by any number of c's.
Example 7
Write the regular expression for the language accepting all the
string in which any number of a's is followed by any number
of b's is followed by any number of c's.
• Solution:
As we know, any number of a's means a* any number of b's means b*, any
number of c's means c*. Since as given in problem statement, b's appear
after a's and c's appear after b's. So the regular expression could be:
R = a* b* c*
Example 8
• Write the regular expression for the language over ∑
= {0} having even length of the string.
Example 8
• Write the regular expression for the language over ∑
= {0} having even length of the string.
Solution:
The regular expression has to be built for the language:
L = {ε, 00, 0000, 000000, ......}
The regular expression for the above language is:
R = (00)*
Example 9
• Write the regular expression for the language
having a string which should have atleast one
0 and alteast one 1.
Example 9
• Write the regular expression for the language
having a string which should have atleast one
0 and alteast one 1.
Solution:
The regular expression will be:
R = [(0 + 1)* 0 (0 + 1)* 1 (0 + 1)*] + [(0 + 1)* 1 (0
+ 1)* 0 (0 + 1)*]
• Describe the language denoted by following
regular expression
RE. = (b* (aaa)* b*)*
• Describe the language denoted by following
regular expression
RE. = (b* (aaa)* b*)*
The language can be predicted from the regular expression by
finding the meaning of it. We will first split the regular
expression as:
r.e. = (any combination of b's) (aaa)* (any combination of b's)
L = {The language consists of the string in which a's appear
triples, there is no restriction on the number of b's}
Problem
Solution
IDENTITIES FOR REGULAR
EXPRESSIONS

`
Which among the following are
incorrect regular identities?
a) εR=R
b) ε*=ε
c) Ф*=ε
d) RФ=R
Answer: d
Explanation: I2: There are few
identities over Regular Expressions
which include: RФ=ФR=Ф
(0+ε) (1+ε) represents
a) {0, 1, 01, ε}
b) {0, 1, ε}
c) {0, 1, 01 ,11, 00, 10, ε}
d) {0, 1}
Answer: a
Explanation: The regular expression is
fragmented and the set of the strings
eligible is formed. ‘+’ represents union
while ‘.’ Represents concatenation.
Which of the following is correct?
Statement 1: ε represents a single string in the set.

Statement 2: Ф represents the language that consist

of no string.

a.Statement 1 and 2 both are correct

b.Statement 1 is false but 2 is correct
c. Statement 1 and 2 both are false
d. There is no difference between both the
statements, ε and Ф are different notation for same
reason
Answer: (a).Statement 1 and 2 both
are correct
Let for ∑= {0,1} R= (∑∑∑) *, the language of R
would be
a.{w | w is a string of odd length}
b.{w | w is a string of length multiple of 3}
c.{w | w is a string of length 3}
d.All of the mentioned
Answer: (b).{w | w is a string of
length multiple of 3}
If ∑= {0,1}, then Ф* will result to:
a. ε
b. Ф
c. ∑
d. None of the mentioned
Regular Expression denote precisely
the ________ of Regular Language.
a) Class
b) Power Set
c) Super Set
d) None of the mentioned
Answer: a
Explanation: Regular Expression
denote precisely the class of regular
language.
Given any regular expression, L(R) is a
regular language.
Given any regular language L, there is
a regular expression R, such that
L(R)=L.
ARDEN’S THEORM

Theorem :
(Arden' s theorem) Let P and Q be two regular expressions
over ∑. If P does not contain Λ, then the following equation in
R, namely
R = Q + RP
has a unique solution (i.e. one and only one solution) given
by R = QP*.
Ardens Theorem
Example 1: Constructing RE for
NDFA
Example 2: Constructing RE for
DFA
Example 3
Example 4
P, O, R be regular expression over ∑, P
is not ε, then
R=Q + RP has a unique solution:
a) Q*P
b) QP*
c) Q*P*
d) (P*O*) *
Arden’s theorem is true for:
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned
Answer: c
Explanation: Arden’s theorem strictly
assumes the following;
a) No null transitions in the transition
diagrams
b) True for only single initial state
Closure Properties of Regular
Language
THEORM

Proof
Q + (QP*)P = Q(Λ+ P*P) = QP* by I9
Important justification
PROBLEM
SOLUTION
PROBLEM & SOLUTION
Difference between Null and Ø
TRANSITION SYSTEM CONTAINING Λ -MOVES

Suppose we want to replace a Λ -move from vertex V1 to vertex V2' Then

we proceed as follows:

Step 1- Find all the edges starting from V2.

Step 2- Duplicate all these edges starting from V1' without changing the edge
labels.

Step 3- If V1 is an initial state, make V2 also as initial state.

Step 4- If V2 is a final state. make V1 also as the final state.

EXAMPLE
EXAMPLE
Construct RE from given FA
Convert this automata with null
moves to automata without it
Construct RE from Finite Automata
answer
• (a + a(b + aa)*b)*a(b + aa)*a
Construct RE from given DFA
Answer
• (ab + ba)*
Construct RE from given DFA, take
q1 as initial state
Answer
• 0*(1*)
Construct RE from given DFA
Answer
• (0 + 1(1 + 01)* 00)*
Construct RE from given DFA

• Q1 as initial state
• (0 + 1(1 + 011)*(00 + 010)*(1(1 + 011)* 01)
Construct FA Equivalent to regular
expression
Construct FA Equivalent to regular
expression
• 10 + (0 + 11)0*1
• (0 +1 )*(00 + 11)(0 + 1)*
Comparison Method
• A language is regular if and only if

a) accepted by DFA
b) accepted by PDA
c) accepted by LBA
d) accepted by Turing machine
• The minimum number of transitions to pass to
reach the final state as per the following
regular expression is:
{a,b}*{baaa}

a) 4
b) 5
c) 6
d) 3
• Which of the following statements is not true?
a) Every language defined by any of the automata is also
defined by a regular expression
b) Every language defined by a regular expression can be
represented using a DFA
c) Every language defined by a regular expression can be
represented using NFA with e moves
d) Regular expression is just another representation for any
automata definition
Equivalence of 2 regular
expression
• Prove (a + b)* =a*(ba*)* by constructing
regular expressions
CONSTRUCTION OF A REGULAR GRAMMAR
GENERATING T(M) FOR A GIVEN DFA M

• Construct a regular grammar G generating the

regular set represented by
• P = a*b(a + b)*.
CONSTRUCTION OF A TRANSITION SYSTEM M
ACCEPTING L(G) FOR A GIVEN REGULAR
GRAMMAR G
• Let G =({Ao, A1,, {a. b}. P, Ao). where P
consists of Ao->aA1,A1->bA1,A1->a,A1->bA0
• Construct a transition system M accepting
L(G).
Minimization of DFA using Myhill-
Nerode Theorem
• Minimization of DFA using Myhill-Nerode Theorem :
Minimization of DFA is Required to obtain the
minimal and equivalent version of any DFA which
consists of minimum number of states possible.
Myhill-Nerode theorem can be used to convert a DFA
to its equivalent DFA with minimum no of states.
This method of minimization is also called Table
filling method. There is also another method called
Partitioning Method or Equivalence Method for the
minimization of DFA
Steps for the Minimization of DFA
• Create the pairs of all the states involved in the given
DFA.
• Mark all the pairs (Qa,Qb) such a that Qa is Final state
and Qb is Non-Final State.
• If there is any unmarked pair (Qa,Qb) such a that
δ(Qa,x) and δ(Qb,x) is marked, then mark (Qa,Qb).
Here x is a input symbol. Repeat this step until no
more marking can be made.
• Combine all the unmarked pairs and make them a
single state in the minimized DFA.
MyHill Nerode Theorem
Minimize given DFA
Pumping Lemma
Pumping Lemma
While applying Pumping lemma over a
language, we consider a string w that
belong to L and fragment it into
_________ parts.
a) 2
b) 5
c) 3
d) 6
If we select a string w such that w∈L,
and w=xyz. Which of the following
portions cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
Answer: b

Explanation: The lemma says, the portion y in xyz cannot be

zero or empty i.e. |y|>0, this condition needs to be fulfilled to
check the conclusion condition
There exists a language L. We define a
string w such that w∈L and w=xyz and
|w| >=n for some constant integer
n.What can be the maximum length of
the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
Answer: a

Explanation: It is the first conditional

statement of the lemma that states
that |xy|<=n, i.e. the maximum length
of the substring xy in w can be n only.
f d is a final state, which of the following is correct according to the given diagra

a) x=p, y=qr, z=s

b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
Let w be a string and fragmented by
three variable x, y, and z as per
pumping lemma. What does these
variables represent?
a) string count
b) string
c) string count and string
d) none of the mentioned
Closure properties of regular sets
• Property 1. The union of two regular set is regular.
• Proof −
• Let us take two regular expressions
• RE1 = a(aa)* and RE2 = (aa)*
• So, L1 = {a, aaa, aaaaa,.....} (Strings of odd length excluding Null)
• and L2 ={ ε, aa, aaaa, aaaaaa,.......} (Strings of even length including
Null)
• L1 ∪ L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,.......}
• (Strings of all possible lengths including Null)
• RE (L1 ∪ L2) = a* (which is a regular expression itself)
• Hence, proved.
Closure properties of regular sets
• Property 2. The intersection of two regular set is regular.
• Proof −
• Let us take two regular expressions
• RE1 = a(a)* and RE2 = (aa)*
• So, L1 = { a,aa, aaa, aaaa, ....} (Strings of all possible lengths excluding
Null)
• L2 = { ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)
• L1 ∩ L2 = { aa, aaaa, aaaaaa,.......} (Strings of even length excluding
Null)
• RE (L1 ∩ L2) = aa(aa)* which is a regular expression itself.
• Hence, proved.
Closure properties of regular sets
• Property 3. The complement of a regular set is regular.
• Proof −
• Let us take a regular expression −
• RE = (aa)*
• So, L = {ε, aa, aaaa, aaaaaa, .......} (Strings of even length
including Null)
• Complement of L is all the strings that is not in L.
• So, L’ = {a, aaa, aaaaa, .....} (Strings of odd length excluding
Null)
• RE (L’) = a(aa)* which is a regular expression itself.
• Hence, proved.
Closure properties of regular sets
• Property 4. The difference of two regular set is regular.
• Proof −
• Let us take two regular expressions −
• RE1 = a (a*) and RE2 = (aa)*
• So, L1 = {a, aa, aaa, aaaa, ....} (Strings of all possible lengths
excluding Null)
• L2 = { ε, aa, aaaa, aaaaaa,.......} (Strings of even length including
Null)
• L1 – L2 = {a, aaa, aaaaa, aaaaaaa, ....}
• (Strings of all odd lengths excluding Null)
• RE (L1 – L2) = a (aa)* which is a regular expression.
Closure properties of regular sets
• Property 5. The reversal of a regular set is regular.
• Proof −
• We have to prove LR is also regular if L is a regular set.
• Let, L = {01, 10, 11, 10}
• RE (L) = 01 + 10 + 11 + 10
• LR = {10, 01, 11, 01}
• RE (LR) = 01 + 10 + 11 + 10 which is regular
• Hence, proved.

• Property 6. The closure of a regular set is regular.

• Proof −
• If L is R* then L* will be (R*)* which is also a regular expression (I8)
• Hence, proved.
Closure properties of regular sets
• Property 7. The concatenation of two regular sets is regular.
• Proof −
• Let RE1 = (0+1)*0 and RE2 = 01(0+1)*
• Here, L1 = {0, 00, 10, 000, 010, ......} (Set of strings ending in 0)
• and L2 = {01, 010,011,.....} (Set of strings beginning with 01)
• Then, L1 L2 =
{001,0010,0011,0001,00010,00011,1001,10010,.............}
• Set of strings containing 001 as a substring which can be
represented by an RE − (0 + 1)*001(0 + 1)*
Equivalence of 2 Regular
Expressions: Example 1
(1 + 00*1) + (1 + 00*1)(1 + 10*1)*(1 + 10*1) =
0*1(1+10*1)*

Take (1 + 00*1) as common

(1 + 00*1) (ε +(1 + 10*1)*(1 + 10*1))
The above equation is of type (ε + R*R) where R = (1 +
00*1). (ε + R*R) can be written as R*
(1 + 00*1)(1 + 10*1)*
Take 1 as common
(ε + 00*)1(1 + 10*1)*
(ε + 00*) can be written as 0*
0*1(1 + 10*1)* =R.H.S.
Example 2
((00*(01)*0) + 0*(10)*)* = (0 + 10)*

From the identity rules (PQ)*P = P(QP)* Substitute the

identity rule in the given equation.
((00*0(10)*) + 0*(10)*)*
We take (10)* common
((00*0 + 0*)(10)*)*
We take (00*0 + 0*) as 0* because RR*=R* and R+R=R
(0*(10)*)*
We use the identity rule (A + B)* = (A*B*)* we write:
(0 + 10)*