School of Computer Engineering, CS21003 Automata Theory 2025

Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

Lecture No-15 to 16 Module-2

FA : Regular Expression, Regular Language
Branch/Section: CSE20, CSE35, 3rd Faculty: Dr. Anil Kumar Swain

Lecture Summary
1. Regular Language, Regular Expression
2. Converting Regular Languages to Regular Expressions
3. Algebraic properties of regular expressions
4. Identities for regular expression
5. Converting Regular Expression to Regular Language
6. Equivalent proof of regular expressions, Simplification of Regular Expressions
7. Closure properties of regular languages
Module-2: FA : Regular Expression, Regular Language, Pumping Lemma
(Dt.22.08.2024)
1 Introduction
1.1 Regular Language :
 The language accepted by some regular expression or finite automata is known as regular
language.
 We know that language have two type finite language and infinite language.
 Finite language is regular because we can construct it’s regular expressions or finite automata.
 Infinite language may or may not be regular language.
Space for class examples

1.2 Regular Expression :

 A regular expression consists of strings of symbols from some alphabet Σ, parentheses (), and
the operators +, . and *.
 Let Σ be a given alphabet. Then
i. Ø, ε and a belong to Σ are all regular expressions. These are called primitive regular
expressions.
ii. If r1 and r2 are regular expressions, so the expressions r1+ r2, r1.r2, r1* and (r1), are also
regular. These are called recursive definitions.
 Definition: A string is a regular expression if and only if it can be derived from the primitive
regular expressions by a finite applications of recursive definition.

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 1
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

1.3 Precedence of Operators in decreasing order: Rules for Specifying Regular Expressions:
 Two operator characteristics determine how operands group with operators:
 Precedence is the priority for grouping different types of operators with their operands.
 Associativity is the left-to-right or right-to-left order for grouping operands to operators that
have the same precedence.
Sl. No. Operator Associativity Remarks
1 ()
2 * LTR Unary
3 . LTR Binary
4 + or | LTR Binary
LTR - Left to Right

1.4 Relationship between Regular Expression and Regular Language

 A language L is known as regular if and only if it is recognized by a finite accepter (FA).
 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.
 In other words, we can say, a language L is known as regular if and only if it is described by a
regular expression (RE).

 If r is a regular expression and let L(r) denote the language associated with r. The language L(r)
denoted by any regular expression r is defined by the following rules.
i. Ø is a regular expression denoting the empty set {}. L(Φ) = {} =Φ
ii. ε is a regular expression denoting {ε}. L(ε) = {ε}
iii. For every a ∈ Σ, a is a regular expression denoting {a}. L(a) = {a}
iv. If r and s are regular expressions, then
L (r + s) = L (r) ∪ L (s)
L (r · s) = L (r). L (s)
L ((r1)) = L (r)
L ( r*) = (L (r))*.

 Example-1: (Converting Regular Languages to Regular Expressions) Some basic regular

expressions (REs) generated from the given languages and their corresponding finite automata
(FA) are as follows. These concepts have already been discussed during the construction of NFAs
in Module 1.
Sl. Language RE Finite Automata (FA)
No.
1 Language accepting a only r = a
over the set Σ = {a}

2 Language accepting all r = a*

combinations of a's, over
the set Σ = {a}

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 2
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

3 language accepting all r = a+

combinations of a's except
the null string, over the set
Σ = {a}
4 Language accepting a or b r = a+b
only over the set Σ = {a, b}

5 Language accepting all r = (a+b)*

strings over the set Σ = {a,
b}
6 Language accepting all r = (a+b)+
strings over the set Σ = {a,
b} except null string.

7 Language accepting ab r = ab
only over the set Σ = {a, b}
8 Language accepting ab or r = ab + bb
bb only over the set Σ= {a,
b}
9 Language accepting any r = (ab + bb)*
combinations of ab or bb
including ε over the set Σ
= {a, b}
10 Accepting all strings r = a(a + b)*b
starting with “a” and end
with “b” over the set Σ =
{a, b}
11 Accepting the set of all (any)1 0|1
(when discussing DFAs,
strings whose second last we write it this way)
symbol is 1 over {0, 1} This can be written
in re
r = (0+1)*1(0+1)
12 Accepting the set of all 1 0|1(any)
strings whose second (when discussing DFAs,
we write it this way)
symbol is 1 over {0, 1} This can be written
in re
r = (0+1)1 (0+1)*
13 Accepting the set of all r = 1(0+1)*01
strings over {0, 1} that
starts with 1 and end with
01.
14 {w | w ∈ Σ* and w contains r = 00* + 11*
only 0’s or only 1’s} =0+ + 1+
In other words, the
acceptance criteria allow
for one or more zeros or
one or more ones.

15 All strings containing the r=(0+1)*000 (0+1)∗

substring 000, over the
alphabet {0, 1}

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 3
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

1.5 Algebraic properties of regular expressions:

Kleene closure is an unary operator and Union(+) and concatenation operator(.) are binary
operators.

a) Commutative: Commutativity is the property of an operator that says we can switch the order of
its operands and get the same result.
If r1, r2 are RE, then
 r1+r2 = r2+r1. For example, for r1 =a and r2 =b, then RE a+ b and b+ a are equal.
 r1.r2 ≠ r2.r1. For example, for r1 = a and r2 = b, then RE a.b is not equal to b.a.

b) Associativity: Associativity is the property of an operator that allow us to regroup the operands
when the operator is applied twice.
If r1, r2, r3 are RE, then
 r1+ (r2+r3) = (r1+r2) +r3
Example:
r1 = a , r2 = b , r3 = c, then
The resultant regular expression in LHS becomes a+(b+ c) and the regular set for the
corresponding RE is {a, b, c}.
For the RE in RHS becomes (a+ b) + c and the regular set for this RE is {a, b, c}, which is same
in both cases. Therefore, the associativity property holds for union operator.

 r1.(r2.r3) = (r1.r2).r3
Example:
r1 = a , r2 = b , r3 = c
Then the string accepted by RE a.(b.c) is only abc.
The string accepted by RE in RHS is (a.b).c is only abc ,which is same in both cases.
Therefore, the associativity property holds for concatenation operator.
 Note: Associativity property does not hold for Kleene closure(*) because it is unary operator.

c) Identity : 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
 In the case of union operators
 if r+ x = r ⇒ x= ∅ as r ∪ ∅= r, therefore ∅ is the identity for +.
 Therefore, ∅ is the identity element for a union operator.
 In the case of concatenation operator –
 if r.x = r , for x= ε
 r.ε = r ⇒ ε is the identity element for concatenation operator(.) .

d) Annihilator: 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.
 If r+ x = x ⇒ r ∪ x= x , there is no annihilator for +
 In the case of a concatenation operator, r.x = x, when x = ∅, then r.∅ = ∅, therefore ∅ is the
annihilator for the (.)operator. For example {a, aa, ab}.{ } = { }

e) Distributed property: 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.
If r1, r2, r3 are regular expressions, then
 r1.(r2+ r3) = r1.r2 + r1.r3 i.e. left distribution
 (r1+r2).r3 = r1.r3 + r2.r3 i.e. Right distribution
 (r1.r2) +r3 ≠ (r1+r3)(r2+r3)

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 4
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

f) Idempotent law : An operator is idempotent if the result of applying it to two of the same values
as arguments is that value.
 r1 + r1 = r1 ⇒ r1 ∪ r1 = r1 , therefore the union operator satisfies idempotent property.
 r1.r1 ≠ r1 ⇒ concatenation operator does not satisfy idempotent property.

g) Closure: If r1 and r2 are regular expressions(RE), then

 r1* is a RE
 r1+r2 is a RE
 r1.r2 is a RE

h) Closure laws :
 (r*)* = r*, closing an expression that is already closed does not change the language.
 ∅* = ε, a string formed by concatenating any number of copies of an empty string is empty
itself.
 r+ = r.r* = r*r, as r* = ε + r + rr+ rrr …. and r.r* = r+ rr + rrr ……
 r* = r*+ ε

i) Identities for regular expression: Two regular expressions p and q are equivalent if p and q
represent same set of strings or they generate the same language.
There are many identities for the regular expression. Let p, q and r are regular expressions.
I1. ∅ + r = r
I2. ∅.r= r.∅ = ∅
I3. ε.r = r.ε =r
I4. ε* = ε and ∅* = ε
I5. r + r = r
I6. r*.r* = r*
I7. r.r* = r*.r = r+
I8. (r*)* = r*
I9. ε +r.r* = r* = ε + r.r*
I10. (p.q)*.p = p.(q.p)*
I11. (p + q)* = (p*.q*)* = (p* + q*)*
I12. (p+ q).r= p.r+ q.r and r.(p+q) = r.p + r.q

 Example-2: Find out the regular expressions over Σ = {0,1} for the following languages.
(Regular Language to Regular Expression)
Sl. Regular Language Regular Expression Remarks
No.
1 {w | w ∈ Σ* and w contains r = 11* = 1+ Contains 1 ‘s means, one one
1’s only} or any number of 1’s..
2 {w | w ∈ Σ* and w contains r = 00* + 11* Here + is for or.
only 0’s or only 1’s}
3 All strings ending with r = (0 + 1)*011
“011”
4 All strings containing the r = (0 + 1)*000(0 + 1)∗
substring 000.
5 Find a regular expression r = 1* 0 1* 0 1* Explanation:
corresponding to the A string in this language
language of all strings over must have at least two 0's.
the alphabet { 0, 1 } that Since any string of 1's can be
contain exactly two 0's. placed in front of the first 0,
behind the second 0 and

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 5
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

between the two 0's, and

since an arbitrasry string of
1's can be represented by the
regular expression 1*, 1*0
1*0 1* is a regular
expression for this language.
6 All strings containing two or r = (0+1)*0(0+1)*0(0+1)* Fix two zeros. Before or
more 0s after 0, if any (0+1)* is
included, then does not
matter. It simply adds 0 and
1’s to the minimum string 00.
7 Strings of length 6 r = (0+1)(0+1)(0+1)(0+1) Not less, not more, exactly 6.
L= { w ∈ Σ* | the length of (0+1)(0+1) = (0+1)6 So each position either 0 or 1
w is 6} is possible.
8 Strings of length 6 or less ε+0+1+00+01+10+11….+ Any .. but limited to 6.
L= { w ∈ Σ* | the length of 111111
w is less than or equal to 6} = (0+1+ ε)6
9 {w | w ∈ Σ* and w is a string r = (00+01+10+11)* First consider minimum
of even length} strings of even length, that is
two. With 2 = 22 = 4
combinations of strings
possible. Then takes Kleeen
closure,
10 Strings containing any r = 0*1*
number of 0 s followed by
any number of 1 s.
11 All strings of alternating 0s r = ( ε + 1 ) ( 0 1 )* ( ε + 0
and 1s )
0r
r = (01)* + (10)* + 0(10)*
+ 1(01)*
12 Regular expression of set of r = (00)*1(11)*
all strings of 0’s and 1’s
having even number of 0’s
followed by odd numbers of
1’s .
13 Find a regular expression for r = (1 + 011)*
representing the set L of
strings in which every 0 is
immediately followed by at
least two 1s.
14 The set of all strings r = (0+1)*0(0+1)*0(0+1)*
containing at least two
0's.
15 All strings containing an r = 1* + (1*01*01*)* The first expression 1*
even number of 0's: describes the strings with no
Either the string does not 0's. The expression
contain any 0’s or it (1*01*01*)* describes the
contains minimum two strings with at least two 0's.
zeros (that is even) with Notice that any 0 must be
any any number of 1’s followed by a matching 0 and

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 6
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

before or after 0’s and its between them there

closure could be zero or more
occurences of 1's.

 Example-3: Find out the regular expressions over Σ = {0,1} for the following languages.
(Regular Language to Regular Expression)
Sl. Regular Language Regular Expression Remarks
No.
1 {w | w ∈ Σ* and w does not r = 0* If it does not contain 1’s
contain 1’s} means only contains 0’s or ∈.
2 All strings with no “0” after r = 1*0* No 0’s after 1, but 1 after
“1” zero possible, only 1*
possible, only 0* possible.. so
is the answer.
3 All strings starting with “1” r = (1 + 10)*
and containing no “00”
4 All strings with at least one r = 00*11* No zero after 1 means, 1 after
“0” and one “1”, and no “0” 1* possible.
after “1
5 All strings not ending in 01. r = ε + 0 + 1 + (0 + 1)* The expression ε+0+1
(00 + 10 + 11) describes the strings with
OR length zero or one, and the
r = ( 0 + 1 )*( 0 + 11 ) expression (0 + 1)* (00 + 10
Any string in a language + 11) describes the strings
over {0 , 1 } must end in 0 with length two or more.
or 1. Hence if a string does
not end with 01 then it
ends with 0 or if it ends
with 1 the last 1 must be
preceded by a symbol 1.
Since it can have any
string in front of the last 0
or 11, ( 0 + 1 )*( 0 + 11) is
a regular expression for the
language.
6 does not contain 11 r = (0+10)* (1+ ε )

7 Write the regular expression r = (0 + 01)*

for the language starting
with 0 but not having
consecutive 1's.
8 Strings with no consecutive r = (1 + 01 )* (0 + ε)
0's
9 Regular Expression of all r = (0+10) * 1*
those Strings that do not
contain the substring 110
10 All strings not containing the r = (1 + 01 + 001)∗
substring 000 (ε + 0 + 00)
11 All strings not containing the r = 0*(1*000*)*1*0*
substring 101

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 7
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

 Example-4: Find out the regular language for the given regular expressions.
(Regular Expression to Regular Language)
Sl. Regular Expression Regular Language
No.
1 r = (a + b)*(a + bb) L(r) ={w ∈ {a,b}* | w end with a or bb}
i.e. All strings end with either a or bb.
2 r = (0 +1)*00 (0 +1)* L(r) ={w ∈ {0,1}* | w contains a substring 00}
i.e. All strings over {0, 1} contains a substring 00.
3 r = (0+1).(00+11) L(r) = L((0+1).(00+11))
=L(0+1).L(00+11)
={0,1}{01, 11}
={000, 011, 100, 111}
4 r = (a + b)a * L(r) = L((a + b)a*)
= L((a + b)) L(a*)
= L(a + b) L(a*)
= {a, b}{∈, a, aa, aaa, …}
= {a,aa,aaa,...,b,ba,baa,...}
5 r = (aa)*(bb)*b Set of strings consisting of even number of a’s followed by
odd number of b’s ,
so L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ……..}
6 r = ( aa + ab + ba + bb )* Language of strings of even lengths over the alphabet of {
a, b }
7 Describe as simply as A string in the language can start and end with a or b, it has
possible in English the at least one b, and after the first b all the b's in the string
language corresponding to appear in pairs. Any number of a's can appear any place in
the regular expression the string. Thus simply put, it is the set of strings over the
a*b(a*ba*b)*a* . alphabet { a, b } that contain an odd number of b's
8 Describe as simply as (( a + b )3) represents the strings of length 3.
possible in English the Hence (( a + b)3)* represents the strings of length a
language corresponding to multiple of 3. Since (( a + b )3)*( a + b ) represents the
the regular expression (( a + strings of length 3n + 1, where n is a natural number, the
b )3)*( ε + a + b ) given regular expression represents the strings of length
3n and 3n + 1, where n is a natural number.
9 Describe as simply as (b+ab)* represents strings which do not contain any
possible in English the substring aa and which end in b, and (a+ab)* represents
language corresponding to strings which do not contain any substring bb. Hence
the regular expression ( altogether it represents any string consisting of a
b + ab )*( a + ab )*. substring with no aa followed by one b followed by a
substring with no bb.
10 Find the shortest string that It can easily be seen that , a, b, which are strings in the
is not in the language language with length 1 or less. Of the strings wiht length 2
represented by the regular aa, bb and ab are in the language. However, ba is not in it.
expression a*(ab)*b*. Thus the answer is ba.
11 r = b*a b*a b The language of all strings over the alphabet { a, b } that
contain exactly two a's.
12 r = ( a + b )*( a + bb ) The language of all strings over the alphabet { a, b } that
do not end with ab.
13 (b + ab)* + (b +ab)*a The language having input alphabets a and b, in which two
a’s do not come together.
14 a(b + ba)* + (b + ba)* The language having input alphabets a and b, in which two
a’s do not come together.

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 8
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

15 What is the regular language The set of all strings containing at least two 0’s.
over the alphabet {0,1} is
described by the regular
expression
r = (0+1)*0(0+1)*0(0+1)*

 Example-5: Prove the following. Show that LHS regular expression is equivalent to RHS
regular expression in each case. (Equivalent proof of regular expressions, Simplification of
Regular Expressions)
a) Prove that the regular expression R =ε + 1*(011)*(1*(011)*)* also describes the same set
of strings as S= (1 + 011)*
Solution:
Let P = 1*(011)*
LHS=R = ε + 1*(011)*(1*(011)*)*
= ε + PP*
= P* using I9
= 1*(011)*
= (Q*T*)* where Q=1, T=011
= (Q + T)* using I11
= (1 + 011)* = S = RHS (Proved)

b) Prove that (1+00*1) + (1 + 00*1)(0 +10*1)*(0 + 10*1) = 0*1(0 + 10*1)*

Solution:
LHS = (1 + 00*1)(ε + (0 + 10*1)*(0 + 10*1)) using I12 (Taking (1 + 00*1) as common)
= (1 + 00*1)(0 + 10*1)* using I9 (Taking r=(0 + 10*1) => I9: ε +r*r =r*)
= (ε + 00*)1(0 + 10*1)* using I12 (taking 1 as common from (1 + 00*1) )
= 0*1(0+10*1)* using I9
=RHS (Proved)

c) Show that (0*1*)*=(0+1)*

Solution:
LHS = (0*1*)*
= { ε,0,00,1,11,111,01,10,……}
= {any combinations of 0’s, any combinations of 1’s, any combinations of 0 and 1, ε}

RHS = (0+1)*
= { ε,0,00,1,11,111,01,10,…..}
= { ε, any combinations of 0’s, any combinations of 1’s, any combinations of 0 and
1}
Hence, it is proved that LHS=RHS

d) Show that (0110+01)(10) ∗≡ 01(10) ∗

Solution:
LHS = (0110+01)(10)∗(Use the identity property for concatenation)
= (0110+01ϵ)(10)∗(Apply the left distributive property)
= (01(10+01ϵ))(10)∗(Use the associative property for concatenation)
= (01)((10+01ϵ)(10)* ) (Apply the right distributive property)
= 01(10(10)*+ϵ(10) *) (Use the identity property of concatenation)
= 01(10(10) *+(10) *) (Use the substitution property)
= 01(10)∗= RHS
Hence, it is proved.

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 9
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

 Example-6: Find the length of the shortest string not in the language (over given alphabet) of
given regular expression.
Sl. Regular Length of Explanation
No. Expression shortest string
NOT in the
language
1 r = a*b*(ba)*a* 3 Reference: GATE-CS-2014-(Set-3)/ Q-65
For the language L(r) = a*b*(ba)*a*
String of length 0 => Null ∈ L
String of length 1 => {a, b} ∈ L
String of length 2 => {aa, ab, ba, bb} ∈ L
String of length 3 => {aaa, aab, aba, baa, abb, bba,
bbb} ∈ L, but {bab}∉L
“bab” is the shortest string not acceptable by given
regular expression whose length is 3.
2 r=a*(ab)*b* 2 It can easily be seen that , a, b, which are strings in
the language with length 1 or less. Of the strings
wih length 2 aa, bb and ab are in the language.
However, ba is not in it. Thus the answer is ba.
3 r= 3 We have two ways to solve this, the first way
(1 +01)* 00 (1 being, check every string starting from 0 length it
+10)* + (1+01)* it is generaged by the regular expression or not.
(0+ε) But if we observe the regular expression carefully,
r is actually broken into two parts.
= (Exactly 1 pair of consecutive zeroes)+(No pair
of consecutive zeroes)
= (At most 1 pair of consecutive zeroes)
So if we can recognize the language, we already
know that the shortest string not generated will be
the shortest string having more than one pair of
consecutive 0's and it is none other than 000. So
the length will be equal to 3

2 Closure properties of regular languages

2.1 Languages Associated with Regular Expressions:

 A language L is known as regular if and only if it is recognized by a finite accepter (FA).
 A language L is known as regular if and only if it is described by a regular expression (RE).
 A language L is recognized by a FA if and only if L is described by a regular expression.
 NFA recognize exactly the regular languages.
 Regular expressions describe exactly the regular languages
 If r is a regular expression and let L(r) denote the language associated with r. The language L(r)
denoted by any regular expression r is defined by the following rules.
v. Ø is a regular expression denoting the empty set {}. L(Φ) = {} =Φ
vi. ∈ is a regular expression denoting {∈}. L(∈) = {∈}
vii. For every a ∈ Σ, a is a regular expression denoting {a}. L(a) = {a}
viii. If r1 and r2are regular expressions, then
L (r1 + r2) = L (r1)∪ L (r2)
L (r1 · r2) = L (r1). L (r2)
L ((r1)) = L (r1)
L ( r1*) = (L (r1))*.

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 10
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

2.2 Closure properties of regular languages

 The word closure is defined as as a set of things.
 Thus, closure properties of regular languages describes the operations implemented on regular
languages which ensure that a new regular language will be produced.
 All regular languages are closed under the following mentioned operations. Kleen star closure,
Union, Intersection, Concatenation, Complement, Reversal, Difference, Homomorphism,
Inverse homomorphism etc.

Closure Under Simple Set Operations

a) Closed Under Complement (L1')
 To show regular language is closure under complementation i.e.If a language L1 is regular
its complement L1' is also regular.
Proof:
Let M = (Q, Σ,δ, q0,F) be a dfa that accepts L1. So L1 is regular. Then the dfa M'= (Q, Σ,δ,
q0,Q-F) accepts L1'.
In the definition of a dfa, we assumed δ* to be a total function, so that δ* (qo,w) is defined for
all w ∈ Σ*. Consequently either δ*(q0,w) is a final state, in which case w ∈ L1, or δ*(q0, w) ∈
Q − F and w ∈ L1'
 Construction of DFA for L1' if L1 is given
Step-1: Construct a DFA for L1. It is important to include the dead state(s) if any while
constructing DFA (L1)
Step-2: The DFA for L1' is obtained by flipping the final states of DFA(L1) to non-final states
and vice-versa.
 Examples on Closed Under Complement (L1')
Example-1: Construct a DFA that do not begins and ends with a over Σ = {a, b}.
Solution:
L1 denote the language containing strings L1' denote the language containing strings
that begins and ends with a over Σ = {a, b} that do not begins and ends with a over Σ =
{a, b}
Step-1:DFA for L1 Step-2: DFA for L1'

Example-2: Construct a DFA that do not starts with 0 over Σ = {0, 1}.
Solution:
Let, L1 = { 0x | x ∈ {0,1}*} = strings that starts with 0
So, L1' = { 1x | x ∈ {0,1}*} U {ε} = strings that do not start with 0

L1 denote the language containing strings L1' denote the language containing strings
that starts with 0 over Σ = {0, 1} that do not start with 0 over Σ = {0, 1}
Step-1:DFA for L1 Step-2: DFA for L1'

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 11
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

b) Closed Under Union

 To show regular language is closure under union i.e.The union of two regular languages, L1
and L2, which are represented as L1 ∪ L2, is also regular.
 L1 ∪ L2 = {x | x ∈ L1 or x ∈ L2 (or both)}
 Let, L1 = {00 , 10, 11, 01} and L2 = {∈ , 10, 100} then L1 ∪ L2 = {∈, 00, 10, 11, 01, 100}
Proof:
If L1 and L2 are regular, then there exist regular expressions r1 and r2 such that L1 = L(r1) and
L2 = L(r2). By definition, r1 + r2 expression is denoting the languages L1 ∪ L2.
 Construction of DFA for (L1 ∪ L2)
Step-1: Construct a DFA for L1 and L2 separately.
Step-2: Do cross product Q x R, where Q is the set of states of L1 and R is the set of states of
L2.Mention each state lebel as prj. If |Q|=m and |R|=n, then (L1 ∪ L2) contains mn states.
Complete the transitions for each state as discussed in the class.
Step-3:Decide Initial and Final State(s) : Initial State = prj where p is an initial state of DFA
(L1) and rj is an initial state of DFA(L2). Final State (s) = prj where either p or rj or both are
final states.
 Examples on Closed Under Union (L1 ∪ L2)
Example-1: Construct a DFA that starts with 0 or ends with 0 over Σ = {0, 1}.
Solution:
Let, L1 = {0x | x ∈ {0,1}*} = strings that start with 0
L2 = {x0 | x ∈ {0,1}*} = strings that end with 0
So, L1 ∪ L2 = {x ∈ {0,1}* | x starts with 0 or ends with 0 (or both)}
Step-1

Step-2 and 3
- For union, at least one original DFA must accept:

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 12
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

For more examples, refer DFA Home Assignment Solution Note.

c) Closed Under Intersection L1 ∩ L2

 To show regular language is closure under intersection i.e.The intersection of of two regular
languages, L1 and L2, which are represented as L1 ∩ L2, is also regular.
 L1 ∩ L2 = {x | x ∈ L1 and x ∈ L2 }
 Let, L1 = {00 , 10, 11, 01} and L2 = {∈ , 10, 100} then L1 ∩ L2 = {10}
Proof:
 Since a language denotes a set of (possibly infinite) strings and we have shown above that
regular languages are closed under union and complementation, by De Morgan's law can be
applied to show that regular languages are closed under intersection too.

L1 and L2 are regular ⇒ L1' and L2' are regular (by Complementation property)
L1' ∪ L2' is regular (by Union property)
L1 ∩ L2 is regular (by De Morgan's law)
As De morgan’s law states

In terms of DFA, we can say that a DFA(L1 ∩ L2) accepts those strings that are accepted by
both DFA(L1) and DFA(L2).
 Construction of DFA for (L1 ∩ L2)
Step-1 &2: Same as union (L1 U L2)
Step-3: Initial state = The state lebeled as both DFAs initial states, Final State (s) = The state
lebeled as both DFAs final states.

 Examples on Closed Under Union (L1 ∩ L2)

Example-1: Construct a DFA that starts with 0 and ends with 0 over Σ = {0, 1}.
Solution:
Let, L1 = {0x | x ∈ {0,1}*} = strings that start with 0
L2 = {x0 | x ∈ {0,1}*} = strings that end with 0
So, L1 ∩ L2 = {x ∈ {0,1}* | x starts with 0 and ends with 0}
Step-1

Step-2 and 3
- For intersection, both original DFAs must accept:

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 13
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

For more examples, refer DFA Home Assignment Solution (AN Series) Note.

d) Closed Under Intersection Reverse (L1R)

 The family of regular languages is closed under reversal. i.e. If L1 is regular, then L1 R is also
regular.
 Let L1 is a language starting with 'a', L1 = {aaa, ab, aaaa, aab, aba, ...}. After taking reversal,
L1R = {aaa, ba, aaaa, baa, aba, ...}. If L1 is the langauge starting with 'a' then L1R is the
language ending with 'a'
 Construction of DFA for (L1R)
Let DFA(L1) denote the DFA of L1. Make the following modifications to construct DFA(L1 R).
Change the start state of DFA(L1) to the final state.
Change the final state of DFA(L1) to the start state.
In case there are more than one final state in DFA(L1), first add a new final state and add ε-
transitions from the final states (which now cease to be final states any more) and perform this
step.
Reverse the direction of the arrows.
L1 -> (DFAR) -> (L1R) -> NFA/DFA
 Examples on Construction of FA for (L1R)
Example-1: If the language L1 is starting with 'a' over {a, b}, then construct a FA that
accepts L1R .
Solution:
Step-1: Construct a DFA for L1

Step-2: Change the final state to initial and intial to final states and reverse the arrows.

Step-3: Remove in case any unreachable states.

But this is not the DFA as A has no output and B we are having two outputs on a. So this is a NFA. If you
want to find out a DFA, then follow the process of conversion of NFA to DFA.

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 14
 School of Computer Engineering, CS21003 Automata Theory 2025
Study Material KIIT University, Bhubaneswar and Formal Language AUTUMN

Sl. Set
Explanation & Proof
No. Operations
e The concatenation of two regular languages, L1 and L2, which are
represented using L1.L2 is also regular and which represents the set of
strings that are formed by taking any string in L1 concatenating it with
L1.L2
any string in L2.
or
L1 = { 0,1 } and L2 = { 00, 11} then L1.L2 = {000, 011, 100, 111}.
L1L2
Proof:
(Concatenati
If L1 and L2 are regular, then there exist regular expressions r1 and r2
on)
such that L1 = L(r1) and L2 = L(r2). By definition, r1r2 is a regular
expression denoting the languages L1L2.

f If L1 is a regular language, then the Kleene closure i.e. L1* is also

regular and represents the set of those strings which are formed by
taking a number of strings from L1 and the same string can be repeated
any number of times and concatenating those strings.
L1*
L1 = { 0,1} = {∈, 0, 1, 00, 01, 10, 11 …….} , then L* is all strings
(Kleen star
possible with symbols 0 and 1 including a null string.
closure)
Proof:
If L1 is regular, then there exist regular expressions r1 such that L1 =
L(r1). By definition, r1* expressions denoting the language L1*.

g if L1 and L2 are regular, then L1 − L2 is necessarily regular.

Proof:
It is obvious from the definition of a set difference that
L1 - L2 = L1 ∩ L2'
L1 - L2 L1 and L2 are regular ⇒ L1 and L2' are regular (by Complementation
(Difference) property)
L1 ∩ L2' is regular (by Intersection property)
As L1 - L2 = L1 ∩ L2'
So, L1 - L2 is regular
In terms of DFA, we can say that a DFA(L1 - L2) accepts those strings
that are accepted by both DFA(L1) and not accepted by DFA(L2).

Note: If you notice any errors, please mail to [email protected] or contact at +91-9938853866

CSE18/CSE29-Lecture Notes of Automata Theory & Formal Language Dr. Anil Kumar Swain, CSE, KIIT University, Bhubaneswar Page 15