Chapter 4: Properties of Regular
Languages∗
Peter Cappello
Department of Computer Science
University of California, Santa Barbara
Santa Barbara, CA 93106
cappello@cs.ucsb.edu
• Please read the corresponding chapter before attending this lecture.
• These notes are supplemented with figures, and material that arises during the lecture in
response to questions.
• Please report any errors in these notes to cappello@cs.ucsb.edu. I’ll fix them immediately.
∗
Based on An Introduction to Formal Languages and Automata, 3rd Ed., Peter Linz, Jones and Bartlett
Publishers, Inc.
1
4.1 Closure Properties of Regular Languages
Closure under Simple Set Operators
Thm. 4.1: If L1 and L2 are regular languages, then so are L1 ∪ L2, L1 ∩
L2, L1L2, L1, and L∗1 .
Proof:
1. Assume that L1 and L2 are regular.
2. Let regular expression r1 and r2 denote L1 and L2, respectively.
3. Then,
• r1 + r2 denotes L1 ∪ L2,
• r1r2 denotes L1L2,
• r1∗ denotes L∗1 .
2
4. Let M = (Q, Σ, δ, q0, F ) be a DFA that accepts L1.
5. Then, M = (Q, Σ, δ, q0, Q − F ) accepts L1.
6. Since regular languages are closed under complement and union, L1 ∪ L2 =
L1 ∩ L2 is a regular language.
3
• Let w = s1s2 · · · sn be a word over Σ. Then, wR denotes the word
sn · · · s2s1, the reverse of w. λR = λ.
• Let L be a language. Then LR denotes LR = {wR : w ∈ L}, called
the reverse of L.
Thm. 4.2: The family of regular languages is closed under reversal.
Proof:
1. Let L be regular, and M = (Q, Σ, δ, q0, {qf }) be an NFA that accepts
it1.
2. We construct M R = (Q, Σ, δ R , qf , {q0}), where δ R is δ with the ori-
entation of the arcs reversed.
3. There is a path from q0 to qf in M if and only if there is a path from
qf to q0 in M R : L(M R ) = LR .
1
We may assume without loss of generality that |F | = 1
4
Closure under Other Operators
Def. 4.1: Let Σ and Γ be alphabets. Then, a function
h : Σ 7→ Γ∗
is called a homomorphism.
• For each symbol in Σ, a homomorphism substitutes a word in Γ∗.
• Let w = s1s2 · · · sn. Then,
h(s1s2 · · · sn) = h(s1)h(s2) · · · h(sn).
• If L is a language on Σ, then its homomorphic image is
h(L) = {h(w) : w ∈ L}.
5
Example:
• Let Σ = {0, 1} and Γ = {a, b, . . . , z}.
• Define h as follows:
h(0) = hello
h(1) = goodbye
• Then, h(010) = hellogoodbyehello.
• The homomorphic image of L = {00, 010} is
h(L) = {hellohello, hellogoodbyehello}.
6
Thm. 4.3: Let h be a homomorphism. If L is a regular language, then
its homomorphic image h(L) is regular. The family of regular languages
therefore is closed under arbitrary homomorphisms.
Proof:
1. Assume that L is regular, and let M be a DFA that accepts L.
2. Construct a generalized transition graph (GTG), based on the tran-
sition graph (TG) for M as follows:
For each symbol, s, that labels an arc in the TG for M , label that
same arc in the GTG with h(s).
3. There is a path labelled w from q0 to some final state qf in the TG
for M if and only if there is a path labelled h(w) from q0 to qf in the
GTG.
7
Def. 4.2: Let L1 and L2 be languages on the same alphabet. Then, the
right quotient of L1 with L2 is defined as
L1/L2 = {x : xy ∈ L1 for some y ∈ L2}.
Example: If
L1 = {anbm : n ≥ 1, m ≥ 0} ∪ {ba}
and
L2 = {bm : m ≥ 1},
then
L1/L − 2 = {anbm : n ≥ 1, m ≥ 0}.
• Draw a TG for L1.
• Identify each state, qi in T G1 such that there exists a y ∈ L2 and
there is a path from qi to a final state in T G1.
8
• There are 2 such states, q1 and q2.
These are the final states in L1/L2.
9
Thm. 4.4: If L1 and L2 are regular languages, then L1/L2 is regu-
lar: The family of regular languages is closed under right quotient with a
regular language.
Proof:
1. Assume that L1 and L2 are regular, and let DFA M = (Q, Σ, δ, q0, F )
accept L1.
d
2. We construct DFA M = (Q, Σ, q0, Fc) as follows.
(a) For each qi ∈ Q, determine if there is a y ∈ L2 such that
δ ∗(qi, y) ∈ F.
(b) This can be done by the following procedure:
i. Construct Mi = (Q, Σ, δ, qi, F ).
d
ii. If L2 ∩ L(M ) 6= ∅ then qi ∈ Fc.
d
3. If x ∈ L1/L2 then x ∈ L(M ).
10
4. If x ∈ L1/L2, there exists a y ∈ L2 such that xy ∈ L1.
5. If xy ∈ L1, then:
• δ(q0, x) = q, for some q ∈ Q
• δ(q, y) ∈ F
• By construction, q ∈ Fc, so M
d
accepts x.
d
6. It similarly is easy to show that If x ∈ L(M ) then x ∈ L1/L2.
11
