Computer Engineering Department

Theory of Computation
TOC

Unit II
Regular Expression

Prof. S. D. Jakkan
 Introduction
• Type 3 Grammar: Regular grammar
• Regular grammar generates Regular Language.
• We can express Regular Language by two ways

Regular Language Notation

Machine Like Description Algebraic Notation

(Finite Automata) (Regular Expression)

Unit 1: Finite Automaton

Unit 2: Regular Expression
 Syllabus for Unit- II
❖Introduction

❖Operators of RE

❖Building RE

❖Precedence of operators

❖Algebraic laws for RE

❖Conversions: NFA to DFA, RE to DFA Conversions: RE to DFA

❖DFA to RE Conversions: State/loop elimination, Arden’s theorem

❖Properties of Regular Languages: Pumping Lemma for Regular languages

❖Closure and Decision properties.

❖Case Study: RE in text search and replace

 Operators of Regular Expression
Regular expression denotes languages. For simple example,

Consider Regular Expression: 01* + 10*

Denotes language consisting of all strings that are either single 0 followed by any number of 1’s or either single 1
followed by any number of 0’s.

Before Describing the regular expression notation we need to learn the three operations on languages that
the operators of regular expression represent.
These operations are:
1. Union
2. Concatenation
3. Closure or iteration
 Operators of Regular Expression
1. The Union of two languages L and M is denoted by either L + M or L ∪ M, is the set of strings that are in
either L or M or both. Most frequently we use ‘+’ operator to denote Union in RE.
For Example: if L ={001, 10, 111} and M= {11, 001} then L + M or L ∪ M = {001 , 10, 111, 11}
2. The Concatenation of two languages L and M is denoted by either L . M (dot) or LM (no operator at all) ,
is the set of string that can be formed by taking any string from L and concatenating it with any string
from M.
For Example: L = {001,10,111} and M = {11, 001} then L.M= { 00111 , 1011, 11111,001001, 10001, }
String from L: 001
111
10 001
String from M: 11
Concatenation of L & M= LM= is001001
00111
1011
11111 *
3. The closure (Kleene closure) of the language 10001
denoted by L is the set of strings that can be formed by
taking any number of strings from L.
*
For Example: If L = {a} then L = {𝝐, a, aa, aaa, aaaa, ………}
+
L = {a, aa, aaa, aaaa, ………}is positive closure
1 2 3
L = {a} , L = {aa} , L = {aaa} ……
 Precedence of Regular Expression Operators
➢ Like other algebras the regular expression operators assumes have an assumed order of “precedence” which
means that operators are associated with their operands in a particular order.
➢ For regular expression following is the order of precedence for operators:
1. The star operator is of highest precedence. That is it applies only to smallest sequence of symbols to its left
that is we formed RE.

2. Next in precedence comes the concatenation or dot operator. After grouping all starts to their operands, we
group concatenation operator to their operand.
Since concatenation is an associative in nature it does not matter in what order we group consecutive
concatenations. But by default you should group them from left. For example aba is grouped as (ab)a

3. Finally, all unions (+ operators) are grouped with their operands.

Since union also as associative in nature it does not matter in what order we group consecutive
concatenations. But by default you should group them from left.
For example a + b + a is grouped as (a + b) + a
 Example of Precedence of Regular Expression Operators
* *
➢ Consider Regular Expression: 01 + 10
➢ For regular expression following is the order of precedence for operators:
1. The star operator is of highest precedence. That is it applies only to smallest sequence of symbols to its left
that is we formed RE.
* *
Hence: : 0 (1 )+ 1 (0 )
1. Next in precedence comes the concatenation or dot operator. After grouping all starts to their operands, we
group concatenation operator to their operand. Since concatenation is an associative in nature it does not
matter in what order we group consecutive concatenations. But by default you should group them from left.
* *
Hence: (0 (1 )) + 1 (0 ) Left to right
* *
(0 (1 )) + (1 (0 ))
3. Finally, all unions (+ operators) are grouped with their operands. Since union also as associative in nature it
does not matter in what order we group consecutive concatenations. But by default you should group them
from left.
* *
Hence ((0 (1 )) + (1 (0 )))
* *
And this is well formed and parenthesised RE for given RE 01 + 10
 Building of Regular Expression
➢ Algebras of all kinds start with some elementary expressions usually constants and/or variables.
➢ Algebras then allow us to construct more expressions by applying certain set of operators to these elementary
expressions and to previously constructed expressions.
➢ Usually some methods of groups of operators with operands such as parenthesis is required as well. We will
apply precedence or regular repression operators.
➢ 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 R1 and R2 written as R1 + R2, is also a regular expression.
3. The concatenation of two regular expressions R1 and R1, written as R1R2, 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.
 Algebraic Laws for Regular Expression
1. Associativity and Commutativity:
Commutativity is the property of an operator that says we can switch the order of its operands and get same result.
Associativity is the property of an operator that allow us to regrouping the operands when operator is applied twice .

• L + M = M + L : This is the commutative law for Union.

• (L + M) + N = L + (M + N) This is the Associative law for union.

Hence Union is Commutative and Associative in nature

• (L . M) . N = L . (M . N) This is the Associative law for concatenation.

• But L.M ≠ M.L

Hence concatenation is Associative in nature but not Commutative in nature.

Prepared by V.S. Kolekar

2. Identities and Annihilators:
An identity for an operator is a value that when the operator is applied to the identity and some other value, the
result is the other value.
For Example in maths 0 is identity for + addition operator: 0+x=x

An annihilator for an operator is value that when the operator is applied to the annihilator and some other
value, the result is the annihilator.
For Example in maths 0 is annihilators for * multiplication operator: 0*x=0
For regular expressions we have:

∅ + L = L + ∅ = L : This asserts that ∅ is identity for union.

εL = Lε = L : This law asserts that ε is identity for concatenation.

∅L = L∅ = ∅ : This law asserts that ∅ is annihilator for concatenation.

These laws are powerful tools for simplification of complex regular expression.

Prepared by V.S. Kolekar

3. Distributive laws:
A distributive law involves two operators and asserts that one operator can be pushed down to be applied to
each argument of the other operator individually.
For regular expressions we have:

L.(M + N) = LM + LN

(M + N).L = ML + NL
4. Idempotent Law:
An operator is idempotent if the result of applying it to two of the same values as arguments is that value.
Idempotent Law for union:
L + L = L If we take the union of two identical expressions, we can replace them by one copy of the expression.
For Example:
10 + 1* + 10 + 1* = 10 + 1*

Prepared by V.S. Kolekar

5. Laws Involving Closures :

a. (L*)* = L*

b. ∅ * = ε ∅ is Empty Set

c. ε* = ε ε is Empty String

d. L+ = L L* = L* L

e. L* = L + + ε

f. (L + M)* = (L* M* )*
Prepared by V.S. Kolekar
• How to write Regular Expression for given
regular set or regular language?

Prepared by V.S. Kolekar

➢ Just revise the meaning of operators of Regular Expression.
1. Star Operator(*): If Language containing word any number of symbol then star operator is used.
For example: Consider language containing set strings having any number of a’s only.
Then RE for given Language is a*
2. Union operator (+): If language containing directly or indirectly word or then union operator used
For example: a. Consider language containing set of strings containing string aa or ba
Then RE for given Language is aa + ba
b. Consider language containing set of strings having any number of a’s or b’s
Then RE for given Language is (a + b) * Because language says a or b
Language also says any number of a or b hence * operator also
3. Concatenation operator (.): If language want some combinations of words in strings then concatenation
operator is used
For Example: Consider language containing set of strings always start with ab.
Because language wants combination of two symbols a and b at
Then RE for given Language is a b (a + b) *
start so a concatenating with b at start

After a b at start any a’s or b’s will be present at the end hence (a+ b)*
Prepared by V.S. Kolekar
➢ Just revise the meaning of operators of Regular Expression.
1. Star Operator(*): If Language containing word any number of symbol then star operator is used.
For example: Consider language containing set strings having any number of a’s only.
Then RE for given Language is a*
2. Union operator (+): If language containing directly or indirectly word or then union operator used
For example: a. Consider language containing set of strings containing string aa or ba
Then RE for given Language is aa + ba
b. Consider language containing set of strings having any number of a’s or b’s
Then RE for given Language is (a + b) * Because language says a or b
Language also says any number of a or b hence * operator also
3. Concatenation operator (.): If language want some combinations of words in strings then concatenation
operator is used
For Example: Consider language containing set of strings always start with ab.
Because language wants combination of two symbols a and b at
Then RE for given Language is a b (a + b) *
start so a concatenating with b at start

After a b at start any a’s or b’s will be present at the end hence (a+ b)*
Prepared by Mr. V.S. Kolekar
Write a regular expression for following regular sets over alphabet {a,b}.
1. Set of strings such that all strings containing ab as substring.
2. Set of string such that all strings containing baa as substring.
3. Set of strings such that all strings always starts with a.
4. Set of strings such that all strings always starts with ab
5. Set of string such that all strings always ends with ba
6. Set of strings such that all strings start and ends with same symbol.
7. Set of strings such that all strings starts with a and ends with b
8. Set of strings such that all strings never ends with aa
9. Set of strings such that all strings never starts with a.
10. Set of strings such that all strings never contains aba as substring

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
1. Set of strings such that all strings containing ab as substring.
Answer: L = {ab, aaaaab, abaaa, bbbbabbbbb,aaabbbabaa….}
Strings containing ab (a+b)* ab (a+b)* If we observe strings in L we can have any number of a’s or b’s
before and after ab

Hence R.E. = (a+b)* ab (a+b)*

2. Set of string such that all strings containing baa as substring.

Answer: L = {baa, aaabaa, abaabaa, bbbbabbabbb, aaabbbabaa….}

If we observe strings in L we can have any number of a’s or b’s

Strings containing baa (a+b)* baa (a+b)* before and after baa

Hence R.E. = (a+b)* baa (a+b)*

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
3. Set of strings such that all strings always starts with a.
Answer: L = {a, ab, aaaaab, abaaa, abbbabbbbb, aaabbbabaa….}
Strings always start with a a (a+b)* If we observe strings in L we can have any number of a’s or b’s
after first a

Hence R.E. = a (a+b)*

4. Set of string such that all strings always starts with ab.
Answer: L = {ab, ababaa, abaabaa, abbbabbabbb, ababbbabaa….}

ab (a+b)* If we observe strings in L we can have any number of a’s or b’s

Strings always start with ab
after ab

Hence R.E. = ab (a+b)*

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
5. Set of strings such that all strings always ends with ba.
Answer: L = {ba, aaaaba, abaaba, abbbabbbbba, aaabbbaba….}
Strings always ends with ba (a+b)* ba If we observe strings in L we can have any number of a’s or b’s
before ba

Hence R.E. = (a+b)* ba

6. Set of string such that all strings always starts with ends with same symbol.
Answer: L = {aa, bb , ababaa, abaabaa, babbab, babbbabab….}

In this language Strings starts with a and ends with a Or Strings starts with b and ends with b
a (a+b)* a + b (a+b)* b

Hence R.E. = a (a+b)* a + b (a+b)* b

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
7. Set of strings such that all strings starts with a and ends with b
Answer: L = {ab, aaaab, abaab, abbbabbbb, aaabbbab….}
Strings always starts with a a (a+b)* b If we observe strings in L we can have any number of a’s or b’s
and ends with b between a and b

Hence R.E. = a (a+b)* b

8. Set of strings such that all strings never ends with aa.
Answer: L = {ε, a, b, ababab, abaabb, babbaaaba, babbbabab….}
Strings never ends with aa means
In this language smallest strings are ε, a, b Or
ends with ab or ba or bb

ε + a+b + (a+b)* (ab + ba + bb) If we observe strings in L we can

have any number of a’s or b’s
before ab or ba or bb
Hence R.E. = ε + a + b + (a+b)* (ab + ba + bb)
Prepared by Mr. V.S. Kolekar
Write a regular expression for following regular sets over alphabet {a,b}.
9. Set of strings such that all strings never starts with a.
Answer: L = {ε , b, bb, baaaab, bbaaa, bbbbabbb,
baabbbabaa….}
Strings never starts with a ε + b (a+b)* If we observe strings in L we can have any number of a’s or b’s
means always start with b after first b

Hence R.E. = ε + b (a+b)*

Home work:
Write a regular expression for following regular sets over alphabet {a,b} for Set of
strings such that all strings never contains aba as substring

Prepared by Mr. V.S. Kolekar

 Answer for Homework:

Write a regular expression for following regular sets over alphabet

{a,b} for Set of strings such that all strings never contains aba as
substring
Answer:
Regular Expression= b*(a*bbb*)*a* b*

• Notice that ‘a’ may be followed by either single a or by bb, and this pattern can be repeated as
many times as we want. This pattern is expressed in (a*bbb*)* .
• The extreme cases where a string can start or end with b's or contain only a's are covered by the
expressions left and right from the pattern (a*bbb*)* .

Prepared by Mr. V.S. Kolekar

➢ Just revise the meaning of star operators of Regular Expression.
1. Star Operator(*): If Language containing word any number of symbol then star operator is used.
For example: Consider language containing set strings having any number of a’s only.
Then RE for given Language is a*
Star Operator is used for Closure or iteration. Iteration means some patterns are repeating in language.
For Example: 1. (aa)* L = {ε, aa, aaaa, aaaaaa, aaaaaaaa………}
That’s Means pattern aa is repeating in all strings of language

For Example: 1. (bab)* L = {ε, bab, babbab, babbabbab, babbabbabbab………}

That’s Means pattern bab is repeating in all strings of language

Lets see more examples on writing RE for given regular expression

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.

1. Set of strings such that all strings containing exactly 2 a’s.

2. Set of strings such that all strings containing exactly 2 consecutive a’s.

3. Set of string such that all strings containing at least 2 a’s.

4. Set of strings such that all strings containing at most 2 a’s.

5. Set of strings such that all strings Set of strings such that all strings containing even number of a’s.

6. Set of string such that all strings Set of strings such that all strings containing number of a’s divisible by 3.

Prepared by Mr. V.S. Kolekar

 Write a regular expression for following regular sets over alphabet {a,b}.
1. Set of strings such that all strings containing exactly 2 a’s.
Answer: L = {aa, bbabbabb aabbbb, bbbaa, bbbbaabbbb,…….}

If we observe strings in L we can have any number b’s

Strings containing exactly 2 a’s (b)* a (b)* a (b)*
before , after a also in between two a’s

Hence R.E. = (b)*a (b)* a (b)*

2. Set of strings such that all strings containing exactly 2 consecutive a’s.
Answer: L = {aa, bbbaabbb, aabbbb, aabbbb, bbbaabbb….}

Strings containing exactly If we observe strings in L we can have any number of b’s
(b)* a a (b)*
2 consecutive a’s before and after aa

Hence R.E. = (b)* aa (b)*

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
3. Set of string such that all strings containing at least 2 a’s.
Answer: L = {aa, ababbabb aababb, bbbaa, bbbbaabbbb,aaabbbabaa….}

If we observe strings in L we can have any number a’s or

Strings containing at least (a+b)* a (a+b)* a (a+b)*
b’s before , after a also in between two a’s
2 a’s

Hence R.E. = (a+b)*a (a+b)* a (a+b)*

4. Set of strings such that all strings containing at most 2 a’s. At most 2 means 0 a’s or 1 a’s or 2 a’s
Answer: L = {ε , b,bb,bbb, bbabb, abbabbb, bbbabbb, bbabbab……} not more than 2 a’s

0 a’s means only any number of b’s OR 1 a’s means 1 a and any number of OR 2 a’s means 2 a and any number
b’s of b’s
b*
+ b* a b* + b* a b* a b*

Hence R.E. = b* + b*a b* + b*a b*a b*

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
5. Set of strings such that all strings Set of strings such that all strings containing even number of a’s.
Answer: L = {ε , b, bbb, aa, baabb, abbababab, abbababa, ……}

Any number of b’s without a is accepted b*

OR +
Strings Containing Even Number
( b* a b* a b* )* Any number of b’s in between iteration on
of a’s means a is multiple of 2 i.e
aa (Start Operator) is accepted.
iteration on aa (Start Operator)

Hence R.E. = b* + (b*a b*a b* )*

Prepared by Mr. V.S. Kolekar

Write a regular expression for following regular sets over alphabet {a,b}.
6. Set of strings such that all strings Set of strings such that all strings containing number of a’s is divisible by 3
Answer: L = {ε , b, bbb, aaa, baabab, abbaabaabab, ababaabaabba, ……}

Any number of b’s without a is accepted b*

OR +

Strings Containing number of a’s Any number of b’s in between iteration on

divisible by 3 means a is multiple ( b* a b* a b* a b* )* aaa (Start Operator) is accepted.
of 3 i.e iteration on aaa (Start
Operator)

Hence R.E. =b*+ (b*a b*a b* a b* )*

Prepared by Mr. V.S. Kolekar

• Conversion of Regular Expression to Finite
Automata

Prepared by Mr. V.S. Kolekar

 FA for Basic Regular Expression
b
1. For R.E. = b* Star means Iteration so we will have loop in FA

a,b
2. For R.E. = (a+b)*

a b
3. For R.E. = ab

a
4. For R.E. = (ab)*
b

a
a,b
5. For R.E. = (a+b) b OR

Prepared by Mr. V.S. Kolekar

5. For R.E. = (aa+ab) a a ,b 6. For R.E. = (ab+bb)
a b

b b

7. For R.E. = (aa+ab)* 8. For R.E. = (ab+bb)*

ε
ε
ε
ε ε

ε ε

Prepared by Mr. V.S. Kolekar

Ex. 1 Design a FA from given regular expression 10 + (0 + 11)0* 1
Answer:
First we will construct the transition diagram for a given regular expression.

Prepared by Mr. V.S. Kolekar

Prepared by Mr. V.S. Kolekar
Ex. 2 Design a NFA from given regular expression 1 (1* 01* 01*)*.
Answer:
First we will construct the transition diagram for a given regular expression.

States I/P 0 1

q0 Ф qf

*qf q2 qf

q2 qf q2

Prepared by Mr. V.S. Kolekar

Ex. 3 Construct the FA for regular expression 0*1 + 10.
Answer:
First we will construct the transition diagram for a given regular expression.

States I/P 0 1

q0 q0 {q1 , q2}

*q1 Ф Ф

q2 q3 Ф

*q3 Ф Ф

Prepared by Mr. V.S. Kolekar

• Conversion of Finite Automata to Regular Expression
by Arden’s Theorem

Prepared by Mr. V.S. Kolekar

 Statement of Arden’s Theorem:
It states that-
Let P and Q be two regular expressions over ∑.
If P does not contain a null string ∈,
then-
R = Q + RP has a unique solution i.e. R = QP*

For Example: A = 01 + A (0*1) Then A= 01(0*1)*

Arden’s Theorem is popularly used to convert a given FA to its regular expression.

Conditions-
To use Arden’s Theorem, following conditions must be satisfied-
1. The transition diagram must not have any ∈ transitions.
2. There must be only a single initial state.
Prepared by Mr. V.S. Kolekar
 Steps to Convert FA to RE by Arden’s Theorem:

To convert a given DFA to its regular expression using Arden’s Theorem, following steps are followed-
Step-01:

➢Form a equation for each state considering the transitions which comes towards that state.
State= source state of input . Input coming to it
➢Add ‘∈’ in the equation of initial state.

Step-02:

➢ Bring final state in the form R = Q + RP to get the required regular expression by Arden’s
theorem as R = Q + RP has a unique solution i.e. R = QP*

Prepared by Mr. V.S. Kolekar

 Important Notes:
Note-01:

➢Arden’s Theorem can be used to find a regular expression for both DFA and NFA.

Note-02:

If there exists multiple final states, then-

➢Write a regular expression for each final state separately.

➢Add all the regular expressions to get the final regular expression.

Prepared by Mr. V.S. Kolekar

• Practice Problems on Conversion of FA to RE

Prepared by Mr. V.S. Kolekar

Ex.1 Find regular expression for the following DFA using Arden’s Theorem-
Answer:
Step-01: i) Form a equation for each state considering the transitions which comes towards that state.
State= source state of input . Input coming to it.
ii) Add ‘∈’ in the equation of initial state.
Form a equation for each state:

A= ε+ B.1 - - - - - - - - (1) A is initial state hence add ‘∈’ in the equation of initial state

B =A. 0 - - - - - - - - (2)

Step – 02: Bring final state in the form R = Q + RP.

B is Final State so simplify B’s Equation by using eq. 1 and 2 B = 0 + B 10
This equation (3) is in the form R= Q + RP
B =A.0 B = (ε + B.1) 0
B = ε0 + B 10 B = 0 + B 10 - - - - - - - - (3) Where R= B, Q = 0 P = 10
By using Identity Law ε.0 = 0
By Arden’s Theorem Solution is R= QP*
Hence B= 0 (10)*
Hence R.E. for Given DFA is : 0 (10)*
Prepared by Mr. V.S. Kolekar
Ex.2 Find regular expression for the following DFA using Arden’s Theorem-
Answer:
Step-01: i) Form a equation for each state considering the transitions which
comes towards that state.
State= source state of input . Input coming to it.
ii) Add ‘∈’ in the equation of initial state.
Form a equation for each state:
q1 = ε - - - - - - - - (1) q1 is initial state hence add ‘∈’ in the equation of initial state
q2 = q1.a - - - - - - - - (2)
q3 = q1.b + q2.a + q3. a - - - - - (3)

Step – 02: Bring final state in the form R = Q + RP. q3 = b + a.a + q3. a
q3 is Final State so simplify q3’s Equation by using eq. 1,2 & 3
This equation (4) is in the form R= Q + RP
q3 = q1.b + q2.a + q3. a q3 = ε.b + q1.a.a + q3. a
Where R= q3, Q = b + aa, P = a
q3 = ε.b + ε.a.a + q3. a q3 = b + a.a + q3. a - - - - - (4)
By using Identity Law ε.b = b & ε.aa = aa By Arden’s Theorem Solution is R= QP*
Hence B= (b + aa) a*
Hence R.E. for Given DFA is : (b+aa)a*
Prepared by Mr. V.S. Kolekar
 Home Work:
Find regular expression for the following DFA using Arden’s Theorem-

Prepared by Mr. V.S. Kolekar

• Pumping Lemma Theorem for Regular Language

Prepared by Mr. V.S. Kolekar

 Statement of Pumping Lemma Theorem:
It states that-
For any regular language L, there exists an integer n,
such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and

(1) |uv| ≤ n

(2) |v| ≥ 1

(3) for all i ≥ 0: uviw ∈ L

In simple terms, this means that if a string v is ‘pumped’, i.e., if v is

inserted any number of times, the resultant string still remains in L

Prepared by Mr. V.S. Kolekar

Statement of Pumping Lemma Theorem:

Prepared by Mr. V.S. Kolekar

Statement of Pumping Lemma Theorem:

Prepared by Mr. V.S. Kolekar

Statement of Pumping Lemma Theorem:

Prepared by Mr. V.S. Kolekar

Statement of Pumping Lemma Theorem:

Prepared by Mr. V.S. Kolekar

Statement of Pumping Lemma Theorem:

Prepared by Mr. V.S. Kolekar

Statement of Pumping Lemma Theorem:

Prepared by Mr. V.S. Kolekar

 For i= all integer
If u vi w ∈ L is satisfied then languages hold pumping lemma and language may be regular

If for i = any integer

u vi w ∈ L is not satisfied then languages doesn’t hold pumping lemma and language is not regular.

Some important Notes:

1. If a language is regular, it always satisfies pumping lemma.

2. If there exists at least one string made from pumping which is not in L, then L is surely not
regular.

3. The opposite of this may not always be true. That is, if Pumping Lemma holds, it does not mean
that the language is regular.

Prepared by Mr. V.S. Kolekar

Examples on Pumping Lemma

Prepared by Mr. V.S. Kolekar

Example1: let us prove L = {0n1n | n ≥ 0} is irregular.
Answer: Let us assume that L is regular, then by Pumping Lemma the above given rules follow.
Now, let x ∈ L and |x| ≥ n. So, by Pumping Lemma, there exists u, v, w such that (1) – (3) hold.

We show that for all u, v, w, (1) – (3) does not hold.

Consider String from given language let x = 04 14 |x| ≥ n consider n = 4

Decompose X into 3 substrings such that x = 0414 = uvw with |uv| ≤ n and |v| ≥ 1.

So, u = 02 V = 0 w = 014 |uv| ≤ 4 and |v| ≥ 1

X= 02 (0)i 014
For i = 0 : X = 02 (0)0 014 X = 02 014 (0)0 Means Absence of 0’s (0)1 : Means one time 0 and so on

X = 0314 ∉ L = L = {0n1n | n ≥ 0}

For i = 0: x = 04 14 ∉ L = L = {0n1n | n ≥ 0} Hence proved that given L is not Regular Language i.e L is irregular

Prepared by Mr. V.S. Kolekar

Example2: let us prove L = {an| n is prime number} is irregular.
Answer: Let us assume that L is regular, then by Pumping Lemma the above given rules follow.
Now, let x ∈ L and |x| ≥ n. So, by Pumping Lemma, there exists u, v, w such that (1) – (3) hold.

We show that for all u, v, w, (1) – (3) does not hold.

Consider String from given language let x = a7 |x| ≥ n consider n = 5

Decompose X into 3 substrings such that x = a7 = uvw with |uv| ≤ n and |v| ≥ 1.

So, u = a3 V = a w = a3 |uv| ≤ 5 and |v| ≥ 1

X= a3 (a)i a3
For i = 0 : X = a3 (a)0 a3 X = a3 a3 (a2)0 Means Absence of a2 (a2)1 : Means one time (a2) i.e aa and so on

X = a6 ∉ L = L = {0n1n | n ≥ 0} Because 6 is not prime number

For i = 0: x = a6 ∉ L = {an| n is prime number} Hence proved that given L is not Regular Language i.e L is irregular

Prepared by Mr. V.S. Kolekar

• Properties for Regular Language
Language classes have two important kinds of properties:

1. Decision properties.

2. Closure properties.
A decision property for a class of languages is an algorithm that takes a
formal description of a language (e.g., a DFA) and tells whether or not
some property holds.
1. Emptiness of Language.
Is the language described is empty?

2. Membership of Language.
Is particular string w in describe language.

3. Equivalence of Language.
Do two descriptions of language actually describe the same language.
1. Emptiness of Language.
Is the language described is empty?
a. Empty language means set of string having no any string i.e Ф
▪ If our representation is any kind of automata, the emptiness question is whether there is
any path whatsoever from the start state to some accepting state. If so language is non
empty.
• While if the accepting states are separated from start state then language is empty.
• Deciding whether we can reach an accepting state from start state is a simple instance of
graph reachability.
• For R = R1 + R2 then L(R) is empty if and only if both L(R1) and L(R2) are empty.
• R=R1.R1. then L(R) is empty if and only if either L(R1) or L(R2) are empty.
• R= R1* then L(R) is non empty; its always includes at least ϵ
2. Membership of Language.
Is particular string w in describe language.
DFA of given language consist of two states.

• Final States is also called as Accepting State

Because after processing last symbol of given string w, if FA reaches to final state
then that string is accepted by FA and string belongs to the language of FA
wϵL
• Non Final State is also called as Non Accepting State
Because after Processing last symbol of given string w, if FA stop or halt at non final
state then that string is not accepted by FA and string doesn’t belong to the language of
FA.
w∉L
3. Equivalence of Language.
Do two descriptions of language actually describe the same language.
• Descriptions of language either in form of DFA or Regular Expression.
• If DFAs of given language are minimum DFAs and they are equivalent then given two description of
language actually describe the same language.
• And same way if RE of given language are equivalent then both language also equivalent.

How to check Equivalence of given two DFAs?

1. Equivalence of DFA can be check by method of equivalence classes of states.
2. Two states p and q from two different DFA are equivalence if and only if after procession same string w
both will reach will to final state or both will reach to non final state then states are called as equivalent states.
3. If states are not equivalence then that states are called as distinguishable states.

How to check Equivalence of given two RE?

1. Simplify both RE by using Arden’s Theorem and algebraic laws of RE. After simplification if R.H.S. and
L.H.S. is same then both REs are equivalent.
 Closure Properties of Regular Languages
The union of two regular language is also regular
The intersection of two regular language is also regular
The complement of given regular language is also regular
The difference between two regular language is also regular
The reversal of given regular language is also regular
The closure (star) of given language is also regular
The concatenation of two regular language is also regular
A homomorphism (substituting strings for symbols) for regular language is also regular
In simple terms regular language is closed under operations union ,intersection, complement, difference,
reversal, closure, concatenation and homomorphism.

So now question is Regular language is not closed under which operations?

Notice that regular languages are not closed under the subset/superset relation.
For example, 0*1* is regular, but its subset {On1n : n >= 0} is not regular
 Syllabus for Unit- II
❖Introduction ✓.

❖Operators of RE ✓.

❖Building RE ✓.

❖Precedence of operators ✓.

❖Algebraic laws for RE ✓ .

❖Conversions: RE to FA ✓ .

❖DFA to RE Conversions: Arden’s theorem ✓.

❖Properties of Regular Languages: Pumping Lemma for Regular languages ✓ .

❖Closure and Decision properties. ✓.