Closure Properties of
Regular Languages
1
Closure properties
The union of two regular language is regular.
The intersection of two regular language is regular.
The complement of a regular language is regular.
The difference of two regular language is regular.
The reversal of a regular language is regular.
The closure (star) of a regular is regular.
The concatenation of a regular languages is regular.
A homomorphism of a regular language is regular.
The inverse homomorphism of a regular language is
regular.
2
1. Closure under Union
Theorem
If L and M are regular languages, then so L U M.
Proof :
This proof is simple. Since L and M are
regular, they have regular expression; say
L=L(R) and M=L(S). Then L U M =L(R+S)
by the definition of the + operator for
regular expressions.
3
Take two languages
L1
Regular language Regular languageL2
LM1 L1 LM 2 L2
NFA
M1 NFA
M2
Single accepting state Single accepting state
4
Example
M1
n 0
a
n
L1 {a b} b
M2
b a
L2 ba
5
L1 L2
M1
NFA for
M2
6
Example
n
NFA for L1 L2 {a b} {ba}
n
L1 {a b}
a
b
L2 {ba}
b a
7
2. Closure under Complementation
Let L and M be languages over . L1Then is the
complement of L, which is the set of strings of *
that are not in L.
In other words, the complement of a language is
everything that is not accepted by the language
over our alphabet. Here is an argument as to
why complementation is closed. To complement
a language:
First construct a DFA for that language
Complement the accepting states of the DFA
Note that this requires there be no missing transitions in
the DFA. If the automaton “dies” on missing edges,
these states will be missing from the complemented DFA
(which should be accepting states).
8
Complement
L1 M1 L1 M1
L1
1. Take the DFA that accepts
2. Make accepting states non-final,
and vice-versa
9
Example
M1
a a, b
n b a, b
L1 {a b}
M1
n a a, b
L1 {a, b} * {a b}
b a, b
10
3.Closure under Intersection
Let L and M be languages over .
Then L M is the language that
contains all strings that are both in L
and M.
To show closure under intersection,
note DeMorgan’s law which states:
L M L M
We have already shown closure under
union and complementation, therefore
we also have closure under
intersection.
11
DeMorgan’s Law:L1 L2 L1 L2
L1 , L2 regular
L1 , L2 regular
L1 L2 regular
L1 L2 regular
L1 L2 regular
12
nother Proof for Intersection Closur
Machine M1 Machine M2
DFA for
L1 DFA for
L2
onstruct a new DFA that accepts M L1 L2
Msimulates in parallel M1
and M2
13
States in M
qi , p j
State in M1 State in M 2
14
DFA M1 DFA M2
q1 a q2 p1 a p2
transition transition
DFA M
q1, p1 a q2 , p2
New transition
15
DFA M1 DFA M2
q0 p0
initial state initial state
DFA M
q0 , p0
New initial state
16
DFA M1 DFA M2
qi pj pk
accept state accept states
DFA M
qi , p j qi , pk
New accept states
Both constituents must be accepting states
17
Example
n 0 m 0
L1 {a b} n m
L2 {ab }
M1 M2
a b
q0 b q1 p0 a p1
a, b b a
q2 p2
a, b a, b
18
Automaton for intersection
n n
L {a b} {ab } {ab}
a, b
q0 , p0 a q0 , p1 b q1, p1 a q2 , p2
b a b a
q1, p2 b q0 , p2 q2 , p1
a b
a, b
19
4.Closure under Difference
Let L and M be languages over . Then L –
M, the difference of L and M, is the set of
strings that are in L but not in M.
To show closure, note that: L – M M=L
. Since we have shown closure under
intersection and complementation, we also
have closure under difference.
20
Product DFA for Difference
0 0
1 0
A B [A,C] [A,D]
0, 1 1
1 1
0
0
1
0 [B,C] [B,D]
1
0
C D
Notice: difference
1
is the empty language
21
5.Closure under Reversal
The reversal of a string a1a2…an is the string written backwards, that is, a nan-1an-2…a1.
We will use wR to denote the reversal of string w. For example, 1011 R is 1101.
The reversal of a language L, written LR, is the language consisting of the reversals of
all its strings. The reversal of a regular language produces another regular language.
We can show this informally using an automaton A for L(A):
Reverse all the edges in the transition diagram for A
Make the start state of A be the only accepting state for the new automaton
Create a new start state p 0 with transitions on ε to what were the original
accepting states of A
This creates a reversed automaton for A, that accepts a string iff A accepts w R.
22
R
NFA for L1
L1 M1 M1
1. Reverse all transitions
2. Make initial state accepting
state
and vice versa 23
Example
M1
a
n
L1 {a b} b
M1
a
R n
L1 {ba } b
24
6.Closure under Concatenation
L1L2
NFA for
M1 M2
25
Example
n n
L1L2 {a b}{ba} {a bba}
NFA for
n
L1 {a b}
a L2 {ba}
b
b a
26
7. Closure under Star Operation
w w1w2 wk
NFA forL * wi L1
1
M1 L1 *
27
Example
n
NFA for
L1* {a b} *
n
L1 {a b}
a
b
28
Homomorphisms
A homomorphism on an alphabet is a
function that gives a string for each symbol in
that alphabet.
Example: h(0) = ab; h(1) = ε.
Extend to strings by h(a1…an) = h(a1)…h(an).
Example: h(01010) = ababab.
29
8.Closure under Homomorphism
What is a homomorphism?
Given a language L with alphabet , A
1
homomorphism h is defined from some
alphabet 2. For symbol(s) a 1, h(a) is
some string from 2.
We apply h to each symbol of a word w from L and
concatenate the results in order to get a new string.
h(L) is the homomorphism of every word in L.
Example: h is the homomorphism from the
alphabet {0,1,2} to the alphabet {a,b}
defined by h(0) = a, h(1) = ab, h(2) = ba.
h(0120) = aabbaa
h(21120) = baababbaa
h(01*2) = a(ab)*ba
30
Closure under Homomorphism
Theorem: If L is a regular language over
alphabet , and h is a homomorphism on ,
then h(L) is also regular.
Informally, if L is turned into a regular
expression, we are substituting a regular
expression for some other regular
expression matching the homomorphism.
The result is still a regular language.
Note: we can expand homomorphisms to
more general substitution, where
substituting a substring in L (instead of an
individual symbol) with some new string
also results in a language that is regular.
31
Given a DFA for L, how to convert it into an FA for h(L)?
FA Construction for h(L)
Replace every edge
“a” by
DFA for L a path labeled h(a)
qF1
in the new DFA
a
q0 qi qj qF2
h(a)
…
qFk
- Build a new FA that simulates h(a) for every symbol a transition in
the above DFA
- The resulting FA (may or may not be a will be for h(L)
33
Inverse Homomorphism
A homomorphism may be applied
backwards; i.e. given the h(L), determine
what L is. This is denoted as h-1(L), or the
inverse homomorphism of L, which results
in the set of strings w in * such that h(w)
is in L.
Note that while applying the homomorphism to a
string resulted in a single string, we may get a
set of strings in the inverse.
For example, if h is the homomorphism from the
alphabet {0,1,2} to the alphabet {a,b} defined
by h(0) = a, h(1) = ab, h(2) = ba.
Given L is the language {ababa} what is h-1(L) ?
We can construct three strings that map into ababa:
h-1={ 022, 110, 102 }
The result of h-1 is also a regular language (see proof in34
