Closure Properties of

Regular Languages

Union, Concatenation, Closure,

Intersection, Difference, Reversal,
Homomorphism, and Inverse
Homomorphism
1
Review Closure Properties
A closure property is a statement that
a certain operation on languages, when
applied to languages in a class (e.g.,
the regular languages), produces a
result that is also in that class.

2
 Closure Under Union
If L and M are regular languages, so is L
 M.
Proof: Let R and S be the REs that define
L and M.
Then R+S is a regular expression whose
regular language is L  M.
Therefore, regular languages are closed
under union
3
 Closure Under
Concatenation and
Closure
Same idea:
RS is a regular expression whose
language is LM; therefore LM is regular.
R* is a regular expression whose
language is L*; therefore L* is regular

4
 Closure Under Intersection
If L and M are regular languages, then
LM is regular.
Proof: Let L and M be DFA’s whose
languages are L and M, respectively.
Construct C = p-DFA of L and M
Make the accepting states of C be the
pairs consisting of accepting states of both
L and M.
String w accepted by p-DFA iff it is
accepted by both DFA(L) and DFA(M) 5
 Product DFA for
Intersection
0 P-DFA(L  M ) 0
L 1 0
A B [A,C] [A,D]
0, 1 1
1 1 0
0
1 0 [B,C] [B,D]
1
M 0
C D
Which state of p-DFA do we
1 choose for the accepting state?

6
 Product DFA for
Intersection
0 P-DFA(L  M ) 0
L 1 0
A B [A,C] [A,D]
0, 1 1
1 1 0
0
1 0 [B,C] [B,D]
1
M 0
C D
String 11 accepted by p-
1 DFA. P-DFA not empty
and defines
(LM ), which is regular.
7
 Closure Under Difference
L– M = strings in L but not M. If L and M
are regular languages, then so is L-M
Proof: Let L and M be DFA’s whose
languages are L and M, respectively.
Construct C = p-DFA of L and M.
Make the accepting states of C be the
pairs where L-state is accepting but M-
state is not.
p-DFA defines the RL of L-M.
8
Product DFA for Difference
L-M
0 p-DFA(L-M)
1 0
L A B 0
[A,C] [A,D]
0, 1
1 1 1
0
0
1 0 [B,C] [B,D]
1
M 0
C D
Which state do we choose as
1 the accepting state?

9
Product DFA for Difference
0 p-DFA(L-M)
1 0
L A B 0
[A,C] [A,D]
0, 1
1 1 1
0
0
1 0 [B,C] [B,D]
1
M 0
C D
p-DFA(L-M) is the empty language
1 in this case. Proof still valid.
We used the same p-DFA to show
that L=M. L-M is RL with no strings
10
Closure Under Complementation: Recall Σ* denotes
all string that can be formed from alphabet Σ.

The complement of a language L (with

respect to an alphabet Σ such that Σ*
contains L) is Σ* – L.
Since Σ* is regular, the complement of a
regular language is regular because it is the
difference of regular languages.

11
 Closure Under Reversal
Given language L, LR is the set of strings whose
reversal is in L.
Example: L = {0, 01, 100}; LR = {0, 10, 001}.
Reversal of all sting in LR are in L
Prove that RLs are closed under reversal:
Let E be a regular expression for L.
We show how to reverse E, to obtain a regular
expression ER for LR.

12
 Reversal of a Regular
Expression
Basis: If E = a, ε, or ∅, then ER = E.
Induction:
If E=F+G, then ER = FR + GR.
If E=FG, then ER = GRFR
If E=F*, then ER = (FR)*.
Example find ER of 0(10)* + 10*

13
 Example: Reversal of a RE
Let E = 0(10)* + 10*.
ER = (0(10)*)R + (10*)R (union rule)
= ((10)*)R 0R + (0*)R1R (concat. rule)
= ((10)*)R 0+ (0*)R1 (basis)
= ((0R1R)*0 + (0R)*1 (closure rules)
= (01)*0 + 0 *1 (basis)

14
 Homomorphisms
A homomorphism on an alphabet is a
function that assigns a string to every
symbol in that alphabet
Example on ={0,1}
Define h(0) = ab h(1) = ε
Extend to strings by h(a1…an) = h(a1)…h(an)
example: h(01010) = ababab
h(L)={h(w)|w is in L}=homomorphism of L
Language formed by applying h to every
string in L
15
 Closure Under
Homomorphism
If L is a regular language, and h is a
homomorphism on its alphabet, then
h(L)= {h(w)|w is in L} is also a regular
language.
Proof: Let E be a regular expression for L.
Apply h to each symbol in E.
Language of resulting RE, h(L), is regular

16
 Exercise:

h(0) = ab; h(1) = ε.

L is the language of RE = 01* + 10*
Find the RE of h(L) and simplify
Do on board

17
h(0) = ab; h(1) = ε.
L is the language of RE = 01* + 10*
RE of h(L)=abε* + ε(ab)*
ε* = ε
ε is the identity under concatenation.
abε*+ε(ab)*=abε+ε(ab)*=ab+(ab)*.
ab is contained in (ab)*
RE for h(L) is (ab)*

18
 Inverse Homomorphism of a
string
h-1(w) notation for inverse homomorphism
of w
w’=h-1(w), iff h(w’)=w
Given h, to answer the question
“Is w’ an inverse homomorphism of w?”,
apply h to every character in w’
If the result is w, then w’=h-1(w)

19
 Inverse homomorphisms
of a language
Let  be the alphabet of L
Let h be a homomorphism defined on 
Let h(L) be a homomorphism defined on L
Let h-1(L) be an inverse homomorphism of
L defined by h(L)
h-1(L) ={w’ in | such that h(w’) is in h(L)}

20
 Finding h-1(L)
Only practical if h(L) contains just a few strings
Suppose h(L) contains w1 and w2
Let h(L) be a homomorphism of L defined on 
h-1(L) consist of all strings w’ that can be
constructed from characters in  such that
h(w’) is w1 or w2
Only practical if  contains just a few characters

21
Example of an h-1(L) problem
Let h(0) = ab; h(1) = ε.
Let h(L) = {abab, baba}
Find h-1(L)

22
 Solution of h-1(L) problem
={0,1}
h(0) = ab; h(1) = ε.
h(L) = {abab, baba}
h-1(L) = {all w defined on {0,1} such that
h(w) is either abab or baba}
No w such that h(w) = baba.
h-1(L) = any w with two 0’s and any
number of 1’s because h(w)=abab
All 1’s become ε that is identity of concat.
23
CptS 317 Fall 2021 Assignment 11

Exercises 4.2.1 (a), (c) and (e) text p 147

h is homomorphism defined on  = {0,1,2} with h(0)=a,

h(1)=ab, and h(2)=ba.

a)Homomorphism of a string: What is h(0120)?

c) Homomorphism of a language defined by RE: If L is

language L(01*2), what is h(L)?

e) Inverse homomorphism of a language:

h(L) has a single string: ababa
h-1(L) has a finite number of strings: What is h-1(L)?

24
25
 Closure of RLs under Inverse
Homomorphism
Proof by construction
Start with DFA(L) = X and h(a)
homomorphism on alphabet  of L
Construct the ih-DFA = Y for h-1(L) with:
• The same set of states.
• The same start state.
• The same final states.
• Input alphabet = the symbols on which
the homomorphism is defined.
• Transition function δY(q, a) =
˄ X(q, h(a))

26
 Example of ih-DFA Construction
Given h(0)=ab, h(1)=and DFA defined on {a,b}
Find ih-DFA
a
B ih-DFA has following properties
States A, B, and C
a
A b b Start state = A
Accepting state = C
b
δY(q, ) = X˄(q, h())
C
a q = A, B, or C
= {0,1}

27
 Example of ih-DFA Construction
Y=ih-DFA defined on {0,1}
X=DFA defined on {a,b}
a 1 Since
h(1) = ε
B B
1
a
A b A 0
b
b 0 Since
C C h(0) = ab
a
1, 0
δY(q, ) = ˄ X(q, h())
28
29
Quiz #4: 10/18/24
Text: Chapter 4
Lecture slides: regular languages 1, 2 and 3
Assignments: 9-11
HW9: pumping lemma
HW10: minimum-state DFA
HW11: Homomorphisms
Other topics:
product DFAs
reversal of regular expressions
inverse homomorphism DFA

30