Closure Properties of Regular

Languages
Union, Intersection, Difference,
Concatenation, Kleene Closure,
Reversal, Homomorphism, Inverse
Homomorphism
1
Properties of Language Classes
! A language class is a set of
languages.
! We have one example: the regular
languages.
! We’ll see many more in the course.
! Language classes have two important
kinds of properties:
1. Closure properties.
2. Decision properties.
2
 Closure Properties
" A closure property of a language class says
that given languages in the class, an operator
(e.g., union) produces another language in
the same class.
" Example: the regular languages are obviously
closed under union, concatenation, and
(Kleene) closure.
! Use the RE representation of languages.
! Note that Asterate operator is also called Kleene
Closure.
3
 Why Closure Properties?
1. Helps construct automata for more
complex languages
2. Helps show languages not to be in the
class.

4
Example: Use of Closure Property
!We can easily prove L1 = {0n1n | n > 0}
is not a regular language.
!L2 = “the set of strings with an equal
number of 0’s and 1’s” is also not
regular, but that fact is trickier to prove.
!Regular languages are closed under Ç.
!If L2 were regular, then L2 ÇL(0*1*) =
L1 would be, but it isn’t.
5
 Closure Under Union
!If L and M are regular languages, so is
L È M.
!Proof: Let L and M be the languages of
regular expressions 𝛼 and 𝛽,
respectively.
!Then 𝛼+𝛽 is a regular expression
whose language is L È M.

6
 Closure Under Concatenation
and Kleene Closure

!Same idea:
! 𝛼𝛽 is a regular expression whose language
is LM.
! 𝛼* is a regular expression whose language
is L*.

7
 Closure Under Intersection
!If L and M are regular languages, then
so is L Ç M.
!Proof: Let A and B be DFA’s whose
languages are L and M, respectively.
!Construct C, the product automaton of A
and B.

8
 Product Automata
!Let 𝐴 = (𝑄! , Σ, 𝛿! , 𝑠! , 𝐹! ) and 𝐵 =
(𝑄" , Σ, 𝛿" , 𝑠" , 𝐹" ).
!Then, 𝐶 = (𝑄! ×𝑄" , Σ, 𝛿, 𝑠! , 𝑠" , 𝐹! ×𝐹" )
!The transition function is defined as
follows:
! 𝛿 𝑞! , 𝑞" , 𝑎 = (𝛿! 𝑞! , 𝑎 , 𝛿" (𝑞" , 𝑎))
!We can show by induction that
𝛿0 (𝑞! , 𝑞" ), 𝑤 = (𝛿0 𝑞! , 𝑤 , 𝛿(𝑞
0 " , 𝑤))
! Homework 9
 Product Automata
!We can then show that 𝐿 𝐶 = 𝐿 𝐴 ∩
𝐿(𝐵).
!𝑤 ∈ 𝐿 𝐶 ⇔ 𝛿0 𝑠! , 𝑠" , 𝑤 ∈ 𝐹! ×𝐹" ⇔
𝛿0 𝑠! , 𝑤 ∈ 𝐹! ∧ 𝛿0 𝑠" , 𝑤 ∈ 𝐹" ⇔ 𝑤 ∈
𝐿 𝐴 ∧ 𝑤 ∈ 𝐿(𝐵)

10
Example: Product DFA for
Intersection
0 0 0
1 0
A B [A,C] [A,D]

1 1
1 1
0
1 [B,C] [B,D]
0 0
1
0
C D 0

11
 Closure Under Difference
" If L and M are regular languages, then so is
L ∖ M = strings in L but not M.
" Proof: Let 𝐴 = (𝑄! , Σ, 𝛿! , 𝑠! , 𝐹! ) and 𝐵 =
(𝑄" , Σ, 𝛿" , 𝑠" , 𝐹" ) be DFA’s whose languages are
L and M, respectively.
" Construct C, the product automaton of A and
B.
" What should be the final states of C?
! 𝐹! ×(𝑄" ∖ 𝐹" )

12
Example: Product DFA for
Difference
0 0 0
1 0
A B [A,C] [A,D]

1 1
1 1
0
1 [B,C] [B,D]
0 0
1
0
C D 0

13
 Closure under Union, Again
!Let C be the product automaton of A
and B.
!What should be the final states of C
such that 𝐿 𝐶 = 𝐿 𝐴 ∪ 𝐿 𝐵 ?
! (𝐹! ×𝑄" ) ∪ (𝑄! ×𝐹" )

14
Closure Under Complementation
!The complement of a language L (with
respect to an alphabet Σ such that Σ*
contains L) is Σ* ∖ L.
!Are regular languages closed under
complementation?
! Since Σ* is regular, the complement of a
regular language is always regular.

15
 Closure Under Reversal
!The reversal of a string 𝑤 = 𝑎! 𝑎" … 𝑎)*! 𝑎)
is 𝑎) 𝑎)*! … 𝑎! .
!Given language L, LR is the language
consisting of reversals of all strings in L.
!Example: L = {0, 01, 100};
LR = {0, 10, 001}.
!We will show how to construct the NFA of
𝐿+ from the NFA of 𝐿.
16
 Closure Under Reversal
" Let 𝑀 = 𝑄, Σ, Δ# , 𝑆, 𝐹 and 𝑁 =
𝑄, Σ, Δ$ , 𝐹, 𝑆 .
" For all 𝑞, 𝑞% ∈ 𝑄, 𝑎 ∈ Σ, 𝑞% ∈ Δ& 𝑞, 𝑎 ⇔ 𝑞 ∈
Δ$ (𝑞% , 𝑎)
" We will show that 𝐿 𝑁 = 𝐿 𝑀 '
" For this, we will first prove that for all 𝑤 ∈
<& {𝑞}, 𝑤 ⇔ 𝑞 ∈ Δ
Σ∗ , 𝑞% ∈ Δ <$ {𝑞% }, 𝑤 '

17
 Lemma-1
" For any NFA (𝑄, Σ, Δ, 𝑆, 𝐹), for all 𝐴 ⊆ 𝑄, 𝑤 ∈
< 𝐴, 𝑤 ⇔ ∃𝑞% . 𝑞% ∈ 𝐴 ∧ 𝑞 ∈ Δ
Σ∗ ,𝑞 ∈ Δ < 𝑞% , 𝑤
Proof: Based on induction on length of 𝑤.
Base Case: 𝑤 = 𝜖.
𝑞∈Δ < 𝐴, 𝜖 ⇒ 𝑞 ∈ 𝐴 . Hence, we take 𝑞% = 𝑞,
since 𝑞 ∈ Δ < 𝑞 ,𝜖 .
< 𝑞% , 𝜖 ⇒ 𝑞% = 𝑞.
Conversely, . 𝑞% ∈ 𝐴 ∧ 𝑞 ∈ Δ
Since Δ < 𝐴, 𝜖 = 𝐴, 𝑞 ∈ Δ
< 𝐴, 𝜖

18
 Lemma-1
Inductive Case: 𝑤 = 𝑥𝑎. By inductive
hypothesis, 𝑞 ∈ Δ < 𝐴, 𝑥 ⇔ ∃𝑞% . 𝑞% ∈ 𝐴 ∧ 𝑞 ∈
< 𝑞% , 𝑥 .
Δ
Let 𝑞 ∈ Δ< 𝐴, 𝑥𝑎
𝑞∈Δ < 𝐴, 𝑥𝑎 ⇒ ∃𝑞%% . 𝑞′′ ∈ Δ
< 𝐴, 𝑥 ∧ 𝑞 ∈ Δ(𝑞%% , 𝑎)
< 𝑞% , 𝑥 ∧ 𝑞 ∈ Δ(𝑞%% , 𝑎)
⇒ ∃𝑞% . 𝑞% ∈ 𝐴 ∧ 𝑞′′ ∈ Δ
⇒ ∃𝑞% . 𝑞% ∈ 𝐴 ∧ 𝑞 ∈ Δ< 𝑞% , 𝑥𝑎
Conversely, let 𝑞% ∈ 𝐴 ∧ 𝑞 ∈ Δ < 𝑞% , 𝑥𝑎

19
 Lemma-1
𝑞% ∈ 𝐴 ∧ 𝑞 ∈ Δ < 𝑞% , 𝑥𝑎
< 𝑞% , 𝑥 ∧ 𝑞 ∈ Δ(𝑞%% , 𝑎)
⇒ 𝑞% ∈ 𝐴 ∧ ∃𝑞%% . 𝑞%% ∈ Δ
< 𝐴, 𝑥 ∧ 𝑞 ∈ Δ(𝑞%% , 𝑎)
⇒ ∃𝑞%% . 𝑞%% ∈ Δ
⇒𝑞∈Δ < 𝐴, 𝑥𝑎

20
 Lemma-2
!For any NFA (𝑄, Σ, Δ, 𝑆, 𝐹), for all 𝑞 ∈ 𝑄,
@ {𝑞}, 𝑎𝑤 = Δ
𝑎 ∈ Σ, 𝑤 ∈ Σ∗ , Δ @(Δ 𝑞, 𝑎 , 𝑤)
Proof: Based on induction on length of 𝑤.
Base Case: 𝑤 = 𝜖. Δ @ {𝑞}, 𝑎𝜖 = Δ@ {𝑞}, 𝑎 =
Δ(𝑞, 𝑎)
@ Δ 𝑞, 𝑎 , 𝜖 = Δ 𝑞, 𝑎
Δ

21
 Lemma-2
Inductive Case: Let 𝑤 = 𝑥𝑏. By inductive
@ {𝑞}, 𝑎𝑥 = Δ
hypothesis, Δ @(Δ 𝑞, 𝑎 , 𝑥).
@ {𝑞}, 𝑎𝑥𝑏 = ⋃ ! /
Then, Δ Δ(𝑞6 , 𝑏) =
- ∈0({-},45)
⋃-! ∈0(0(-,4),5)
/ Δ(𝑞 @(Δ 𝑞, 𝑎 , 𝑥𝑏).
6 , 𝑏) = Δ

22
 Closure under Reversal
!We will now prove that for all 𝑤 ∈
@7 {𝑞}, 𝑤 ⇔ 𝑞 ∈ Δ
Σ∗, 𝑞6 ∈ Δ @8 {𝑞6 }, 𝑤 +
Proof: Based on induction on length of 𝑤.
Base Case: 𝑤 = 𝜖.
@7 {𝑞}, 𝜖 ⇔ 𝑞 = 𝑞6 ⇔
In this case, 𝑞6 ∈ Δ
𝑞∈Δ @8 {𝑞6 }, 𝜖

23
 Closure under Reversal
Inductive Case: Let 𝑤 = 𝑥𝑎. By inductive
<& {𝑞}, 𝑥 ⇔ 𝑞 ∈
hypothesis, for all 𝑞, 𝑞′, 𝑞% ∈ Δ
<$ {𝑞% }, 𝑥 ' .
Δ
<& {𝑞}, 𝑥𝑎 ⇔ ∃𝑞%% ∈ Δ
𝑞% ∈ Δ <& {𝑞}, 𝑥 . 𝑞% ∈ Δ# 𝑞%% , 𝑎
⇔𝑞∈Δ <$ {𝑞%% }, 𝑥 ' ∧ 𝑞%% ∈ Δ$ (𝑞% , 𝑎)
⇔𝑞∈Δ <$ Δ$ 𝑞% , 𝑎 , 𝑥 '
⇔𝑞∈Δ <$ ({𝑞% }, 𝑎𝑥 ' )

24
 Closure Under Reversal
<& ({𝑞}, 𝑤)
𝑤 ∈ 𝐿 𝑀 ⇔ 𝑞 ∈ 𝑆 ∧ 𝑞% ∈ 𝐹 ∧ 𝑞% ∈ Δ
<$ {𝑞% }, 𝑤 '
⇔ 𝑞 ∈ 𝑆 ∧ 𝑞% ∈ 𝐹 ∧ 𝑞 ∈ Δ
⇔ 𝑤 ' ∈ 𝐿(𝑁)

25
Reversal of a Regular Expression
!Basis: If E is a symbol a, ε, or ∅, then
ER = E.
!Induction: If E is
! F+G, then ER = FR + GR.
! FG, then ER = GRFR
! F*, then ER = (FR)*.

26
 Homomorphisms
!A homomorphism from alphabets Σ to Γ
is a function that maps each symbol in
Σ to a string in Γ ∗ .
!Example: h(0) = ab; h(1) = ε.
!Extend to strings by h(a1…an) =
h(a1)…h(an).
!Example: h(01010) = ababab.

27
Closure Under Homomorphism
!If L is a regular language, and h is a
homomorphism on its alphabet, then h(L)
= {h(w) | w ∈ L} is also a regular
language.
!To prove this, we will use the
representation as regular expressions.

28
Closure Under Homomorphism
!Let 𝛼 be the regular expression for L.
!ℎ 𝛼 is defined inductively:
! h a =h(a)
! ℎ 𝜖 =𝜖
! ℎ ∅ =∅
! ℎ 𝛽 + 𝛾 = ℎ 𝛽 + ℎ(𝛾)
! ℎ 𝛽𝛾 = ℎ 𝛽 ℎ 𝛾
! ℎ 𝛽∗ = ℎ 𝛽 ∗
29
Closure under Homomorphism
!Note that 𝛼 is a regular expression over
Σ, while ℎ(𝛼) is a regular expression
over Γ.
!Proof is based on following
observations:
! ℎ 𝐿𝑀 = ℎ 𝐿 ℎ(𝑀)
! ℎ ⋃) 𝐿) = ⋃) ℎ(𝐿) )

30
 Example: Closure under
Homomorphism
!Let h(0) = ab; h(1) = ε.
!Let L be the language of regular
expression 01* + 10*.
!Then h(L) is the language of regular
expression abε* + ε(ab)*.
! Equivalent to (ab)*.

31
 Inverse Homomorphisms
!Let h be a homomorphism from Σ to Γ
and 𝐿 ⊆ Γ ∗ .
!h-1(L) = {w ∈ Σ∗ | h(w) ∈ L}.

32
Example: Inverse Homomorphism
!Let h(0) = ab; h(1) = ε.
!Let L = {abab, baba}.
!h-1(L) = the language with two 0’s and
any number of 1’s = L(1*01*01*).

33
 Closure Proof for Inverse
Homomorphism
!We will use the DFA representation of
regular languages.
!Start with a DFA 𝑀 = (𝑄, Γ, 𝛿7 , 𝑠, 𝐹) for L.
!The DFA 𝑁 for ℎ*! (𝐿) is defined as
follows: 𝑁 = (𝑄, Σ, 𝛿8 , 𝑠, 𝐹)

34
 Closure Proof for Inverse
Homomorphism
!The transition function 𝛿8 is defined in
terms of 𝛿7 :
! 𝛿& 𝑞, 𝑎 = 𝛿M$ (𝑞, ℎ(𝑎))

35
Example: Inverse Homomorphism
Construction
a
B
a
A b b
b
C
a

h(0) = ab
h(1) = ε 36
Example: Inverse Homomorphism
Construction
a 1

B B
1
a
A b A 0
b
b 0
C C
a
1, 0
h(0) = ab
h(1) = ε 37
 Proof of Correctness
!We can show by induction that for
𝑤 ∈ Σ∗ , 𝛿08 𝑠, 𝑤 = 𝛿07 𝑠, ℎ 𝑤 .
!Then, it directly follows that
𝑤 ∈ 𝐿 𝑁 ⇔ 𝑤 ∈ ℎ*! (𝐿(𝑀))

38
 An Application of closure
under homomorphism
!Consider an 𝜖-NFA 𝑀 = (𝑄, Σ9 , Δ, 𝑆, 𝐹).
! We will use homomorphism to show that
the language of M is regular.
!Consider ordinary NFA 𝑀9 = (𝑄, Σ ∪
𝜖 , Δ, 𝑆, 𝐹).
! Here, we use 𝜖 as a symbol, and not the
empty string.

39
 An Application of closure
under homomorphism
!Now, we define the homomorphism
ℎ: Σ ∪ 𝜖 → Σ∗ :
! ℎ 𝑎 = 𝑎, for 𝑎 ∈ Σ
! ℎ 𝜖 =𝜖
!Notice that ℎ 𝐿 𝑀9 =𝐿 𝑀 .
!Since 𝐿 𝑀9 is regular, and regular
languages are closed under
homomorphism, 𝐿 𝑀 is also regular.
40
 Subtle point
!If 𝐿 is regular, then ℎ 𝐿 is regular
!If 𝐿 is regular, then ℎ*! 𝐿 is regular
!If ℎ(𝐿) is regular, then is 𝐿 regular?
! No! ℎ*! ℎ 𝐿 ≠𝐿
! Consider 𝐿 = {0+ 1+ |𝑛 ≥ 0}. ℎ 0 = ℎ 1 =
0.
! ℎ 𝐿 = {0+ |𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛} is regular. L is not
regular
! ℎ*! ℎ 𝐿 = {w ∈ 0,1 ∗ | 𝑤 𝑖𝑠 𝑒𝑣𝑒𝑛} 41