Properties of Regular

Languages
Regular Language Properties

1
Topics

• Regular Language Properties

• Closure
• Membership and Equality
• Identifying Non-regular Languages
• Pumping Lemma

2
Regular Language Properties

3
Closure properties of Regular Languages

• What is closure property?

• A set is closed w.r.t. an operation, if applying the operation to its
elements will always give an element of the same set.

• Is the family of regular languages closed under union?

• i.e., if L1 and L2 are regular, is L1 ∪ L2 also regular?

4
Closure under Simple Set Operations
Theorem 4.1

C
• If L1 and L2 are regular languages, then so are L1 ∪ L2, L1 ∩ L2, L1 ⋅ L2, L1 ,
L*1
.

• The family of regular languages is closed under union, intersection,

concatenation, complementation, and star-closure.

5
Closure under Simple Set Operations
Theorem 4.1

• Proof: If L1 and L2 are regular, we can find regular expression r1 and r2 s.t. L1 = L(r1) and
L2 = L(r2).

• By definition, r1 + r2, r1r2, and r*

1
are R.E. for L1 ∪ L2 , L1 ⋅ L2 , and L*
1
respectively.

• Hence these languages are regular.

• To show closure under complementation, let M = (Q, Σ, δ, q0, F) be a DFA that accepts L1.
̂ C
• Then M = (Q, Σ, δ, q0, Q − F) accepts L1 .
• δ* is a total function in DFA, hence ∀w ∈ Σ*, δ*(q0, w) is defined.
• δ*(q0, w) is either a final state or non-final state.
6
Closure under Simple Set Operations
Theorem 4.1

• For closure under intersection, we will give a constructive proof.

• Let L1 = L(M1) and L2 = L(M2), where M1 = (Q, Σ, δ1, q0, F1) and
M2 = (P, Σ, δ2, p0, F2) are DFAs.
We can think of a combined automaton M ̂ = ( Q ,̂ Σ, δ ,̂ (q0, p0), F )̂ , where
Q ̂ = Q × P, δ ̂ is s.t. M ̂ is in state (qi, pj) whenever M1 is in state qi and M2 is in
•

state pj.

• i.e., for δ1(qi, a) ̂ i, pj), a) = (qk, pl).

= qk and δ2(pj, a) = pl, δ ((q

• Then, w ∈ L1 ∩ L2 iff. it is accepted by M .̂

7
Closure under Simple Set Operations
Example 4.1

• Show that the family of regular languages is closed under difference.

• i.e., if L1 and L2 are regular, L1 − L2 is also regular.
• Proof:
C
• L1 − L2 = L1 ∩ L2 .
• This is straightforward using Theorem 4.1.

8
Closure under Simple Set Operations
Theorem 4.2

• The family of regular languages is closed under reversal.

• Proof: You can think of a constructive proof.
• Suppose M = (Q, Σ, δ, q0, F) is an NFA with a single final state.
• i.e., F = {qf}.
̂ ̂ R
• Then we can construct M = (Q, Σ, δ , qf , {q0}), which accepts w for all
w ∈ L(M).
R
• Hence if L is regular, L is also regular, which completes the proof.
9
Closure under Other Operations
Definition 4.1

• Suppose Σ and Γ are alphabets. Then a function

• h : Σ → Γ*
• is called a homomorphism.
• A homomorphism is a substitution in which a single letter is replaced with a string.
• We can easily extend its domain to strings; if w = a1a2⋯an, then
• h(w) = h(a1)h(a2)⋯h(an).
• If L is a language on Σ, then its homomorphic image is defined as
• h(L) = {h(w) : w ∈ L}.
10
Closure under Other Operations
Example 4.2

• Let Σ = {a, b} and Γ = {a, b, c} and define h by

• h(a) = ab
• h(b) = bbc.
• Then h(aba) = abbbcab.
• The homomorphic image of L = {aa, aba} is the language
• h(L) = {ababa, abbbcab}.
11
Closure under Other Operations
Example 4.3

• Take Σ = {a, b} and Γ = {b, c, d}. Define h by

• h(a) = dbcc
• h(b) = bdc.
• If L is a regular language denoted by
• r = (a + b*)(aa)*, then
• r1 = (dbcc + (bdc)*)(dbccdbcc)*
• denotes the regular language h(L).
12
Closure under Other Operations
Theorem 4.3

• Let h be a homomorphism. If L is a regular language, then its homomorphic image h(L) is

also regular.

• The family of regular languages is closed under arbitrary homomorphisms.

• Proof: Let L be a regular language denoted by some regular expression r.
• We can easily obtain h(r) by substituting h(a) for all a ∈ Σ.
• Then it is obvious that h(r) is also a regular expression.
• Now what we have to do is showing that L(h(r)) = h(L).
• For every w ∈ L, there is v = h(w) and v ∈ L(h(r)), and vice versa.
13
Closure under Other Operations
Definition 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}. (4.1)
• Consider all prefixes and suffixes of L1.
• By removing all suffixes belonging to L2, we can obtain L1 /L2.

14
Closure under Other Operations
Example 4.4

n m m
• If L1 = {a b : n ≥ 1,m ≥ 0} ∪ {ba} and L2 = {b : m ≥ 1}, then
n m
• L1 /L2 = {a b : n ≥ 1,m ≥ 0}.
• e.g.) aaabb ∈ L1, and b ∈ L2, bb ∈ L2.
• Hence aaab, aaa ∈ L1 /L2.
• How about ba?
• {λ, a, ba}
15
Closure under Other Operations
Theorem 4.4

• If L1 and L2 are regular languages, then L1 /L2 is also regular.

• The family of regular languages is closed under right quotient with a
regular language.

• Proof: We will consider a constructive proof, which gives a new DFA for
L1 /L2, from DFAs for L1 and L2.

• Let L1 = L(M), where M = (Q, Σ, δ, q0, F) is a DFA.

• We construct another DFA M ̂ = (Q, Σ, δ, q0, F )̂ for the right quotient.

16
Closure under Other Operations
Theorem 4.4

• For each qi ∈ Q, check if there exists a y ∈ L2 s.t. δ*(qi, y) = qf ∈ F.

• Finding δ*(qi, y) = qf ∈ F can be done by checking Mi = (Q, Σ, δ, qi, F).
• Now we need to check whether such y is also in L2.
• i.e., y ∈ L2 ∩ L(Mi).
• We already know how we can build a DFA for the intersection.
• If there is any path between its initial vertex and any final vertex, add qi to F .̂
17
Closure under Other Operations
Theorem 4.4

• Now we need to prove that L( M )̂ = L1 /L2.

• Let x be any element of L1 /L2. Then there must be a y ∈ L2 s.t. xy ∈ L1.
• This implies that δ*(q0, xy) ∈ F,
• and there must be q ∈ Q s.t. δ*(q0, x) = q and δ*(q, y) ∈ F.
• Hence, by construction, q ∈ F ,̂ and M ̂ accepts x.
• Conversely, for any x accepted by M ,̂ we have δ*(q0, x) = q ∈ F .̂

• By construction, there exists a y ∈ L2 s.t. δ*(q, y) ∈ F.

• Combine all these together, L( M )̂ = L1 /L2.
18
Closure under Other Operations
Example 4.5

• Find L1 /L2 for L1 = L(a*baa*), L2 = L(ab*).

• L1 /L2 = L(a*ba*).

Figure 4.3 A DFA for L1 Figure 4.4 A DFA for L1 /L2

19
Elementary Questions about Regular Languages

• All these knowledges about languages are of no use, if we don't have proper
means to answer some questions.

• Given a language L and a string w, whether w is in L or not? (membership)

• Given two languages L1 and L2, whether L1 = L2? (equality)

20
Elementary Questions about Regular Languages
Theorem 4.5

• Given a standard representation of any regular language L on Σ and any

w ∈ Σ*, there exists an algorithm for determining whether or not w is in L.
• We say that a regular language is given in a standard representation,
• iff. it is described by a finite automaton, a regular expression, or a regular
grammar.

• Which are the sufficiently well-defined forms for use in theorems.

• Proof: We can always construct a DFA for the language, and verify whether w
is accepted by it.
21
Elementary Questions about Regular Languages
Theorem 4.6

• There exists an algorithm for determining whether a regular language, given in

standard representation, is empty, finite, or infinite.

• Proof: Again, we can represent the language as a transition graph of a DFA.

• If there is a simple path from the initial vertex to any final vertex, then the
language is not empty.

• If there is any vertex which is the base of some cycle, and it is on a path from
an initial to a final vertex, the language is infinite. Otherwise, it's finite.

22
Elementary Questions about Regular Languages
Theorem 4.7

• Given standard representations of two regular languages L1 and L2, there exists
an algorithm to determine whether or not L1 = L2.

• Proof: Using L1 and L2, we define the language

C C
• L3 = (L1 ∩ L2 ) ∪ (L1 ∩ L2).

• Using closure property, we know L3 is regular, and there is a DFA M accepting it.
• Now we can check whether L3 is empty (by Theorem 4.6), and L3 is empty iff.
L1 = L2.
23
Identifying Non-regular
Languages

24
Identifying Non-Regular Language

• Regular languages are associated with finite automata.

• We can assume that there exist some limitations on the structure of a regular language.
• Intuitively, we can guess that a language is regular only if,
• the information that has to be remembered while processing any string is strictly
limited.

• Otherwise, we can say that the language is not regular.

• Is this argument true?
• We will find out throughout this lecture.
25
Pigeonhole principle

• There are m pigeonholes and n pigeons, and n > m.

• Then some of the pigeons must share their pigeonholes
together, in order to put every pigeon into the holes.

• This principle can be used in many cases.

• e.g.) How many people have the same birthday?
• With 400 people, at least 34 people cannot have
different birthday from the others.

26
Using the Pigeonhole Principle
Example 4.6

n n
• Is the language L = {a b : n ≥ 0} regular? - No it's not.
• Suppose L is regular.
• Then we can find DFA M = (Q, {a, b}, δ, q0, F).
i
• Consider δ*(q0, a ) for i = 1,2,3,⋯.
• With a finite number of states, there must be some state q s.t.,
n m
• δ*(q0, a ) = q, and δ*(q0, a ) = q, with n ≠ m. (pigeonhole principle)
n n n
• Since M accepts a b , we must have δ*(q, b ) = qf ∈ F.
m n n
• Then, δ*(q0, a b ) = δ*(q, b ) = qf , which contradicts the assumption that n = m.
27
Pumping Lemma
Theorem 4.8

• Let L be an infinite regular language. Then there exists some positive integer
m s.t. any w ∈ L with | w | ≥ m can be decomposed as
• w = xyz, with | xy | ≤ m, and | y | ≥ 1, s.t.
i
• wi = xy z, is also in L for all i = 0,1,2,⋯.
• We can say that y is "pumped", which means that repeating this middle part
yields another string in L.

28
Pumping Lemma
Theorem 4.8

• Proof: If L is regular, we can find a DFA for it.

• Let the DFA has states q0, q1, q2, ⋯, qn.
• Take a string w ∈ L, s.t. | w | ≥ m = n + 1.
• Consider states we have to go through while processing w,
• q0, qi, qj, ⋯, qf.
• Since this sequence has exactly | w | + 1 entries, at least one state must be
repeated, no later than the n-th move.
29
Pumping Lemma
Theorem 4.8

• Hence the sequence must look like

• q0, qi, qj, ⋯, qr, ⋯, qr, ⋯, qf.
• Then there must be substrings x, y, z of w,
• δ*(q0, x) = qr, δ*(qr, y) = qr, δ*(qr, z) = qf,
• with | xy | ≤ n + 1 = m and | y | ≥ 1.
2
• It immediately follows that δ*(q0, xz) = qf, δ*(q0, xy z) = qf , and so on.
30
Pumping Lemma
Example 4.7

n n
• Use the pumping lemma to show that L = {a b : n ≥ 0} is not regular.
• Any w ∈ L with | w | ≥ m can be w = xyz, with y can be pumped.
• Assume that L is regular - so that we can use the pumping lemma.
• We can choose n = m, hence the substring y must consist entirely of a's.
• Suppose | y | = k. Then the string obtained by using i = 0 gives
m−k m
• w0 = a b , which is clearly not in L.

31
Applying Pumping Lemma

• We have to be careful when applying the pumping lemma.

• It guarantees the existence of m as well as the decomposition xyz.
• But we don't know the exact m and xyz.
• i.e.) There exists some positive integer m ...
• We cannot claim a contradiction if the lemma is violated for a specific value m or xyz.
• However, we can do it for just one w or i.
i
• i.e.) any w ∈ L ... wi = xy z, is also in L for all i = 0,1,2,⋯.
32
Applying Pumping Lemma
Game Visualization

• The correct argument can be visualized as a game for a given language.

• Winning the game means the language is not regular.
• There are four steps in the game.
1. The opponent picks m. Note that this is not a specific number.

2. Given m, we pick a string w in L, where | w | ≥ m.

3. The opponent chooses xyz, subject to | xy | ≤ m, | y | ≥ 1.
4. We try to pick i in such a way that wi is not in L. If we can, we win the game.

33
Applying Pumping Lemma
Example 4.8

R
• Show that L = {ww : w ∈ Σ*} is not regular.
• In Step 2, we choose a string w of the following form.

• Due to the restriction | xy | ≤ m, the opponent is restricted to choosing a y entirely with

a's.
• Then we use i = 0 in Step 4. The string obtained from it always has fewer a's on the
left than on the right.
r
• Hence it cannot be of the form ww .
34
Applying Pumping Lemma
Example 4.10

n k
• The language L = {(ab) a : n > k, k ≥ 0} is not regular.
m+1 m
• Given m, we pick w = (ab) a , which is in L.
• If the opponent picks y = a, we choose i = 0 and get a string not in L((ab)*a*).
m m
• For y = ab, choose i = 0 again and get the string (ab) a , which is also not in
L.
• For y = aba, we will have consecutive a's, which makes it not in L.
• For any other choices, they are covered by the above cases similarly.
35
Applying Pumping Lemma
Example 4.11

n
• Show that L = {a : n is a perfect square} is not regular.

36
Using Closure Properties
Example 4.12

n k n+k
• Show that L = {a b c : n ≥ 0,k ≥ 0} is not regular.
• We can use closure under homomorphism.
• Take h(a) = a, h(b) = a, h(c) = c,
• then
n+k n+k i i
• h(L) = {a c : n + k ≥ 0} = {a c : i ≥ 0}
• We already know that this is not regular (Example 4.7).
• Try to show it with the pumping lemma, and check Example 4.13 as well.
37
Summary

• After the lectures of this week,

• You should understand closure properties of regular languages.
• You should be familiar with constructive proofs.
• You should be able to find an algorithm regarding regular languages and
standard representations, based on theorems we've learned.

• Understand the pumping lemma, and practice to apply it.

• Consider other methods to show that a given language is not regular.

38