FIT2014 Theory of Computation Lecture 11 (A) Closure properties; (B) Pumping Lemma for Regular Languages
Monash University
Faculty of Information Technology
FIT2014 Theory of Computation
Lecture 11
(A) Closure properties;
(B) Pumping Lemma for Regular Languages
slides by Graham Farr
based in part on previous slides by David Albrecht
COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
Warning
This material has been reproduced and communicated to you by or on behalf of Monash University
in accordance with s113P of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act.
Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act.
Do not remove this notice.
1 / 22
Overview
I Closure properties of regular languages
I Circuits in FAs
I Pumping Lemma
I Non-regular Languages
2 / 22
Closure properties of regular languages
Definition
If doing some operation on regular languages always produces another regular language,
then we say that the class of regular languages is closed under that operation.
We will see that regular languages are closed under:
I complement
I union
I intersection
I concatenation
Theorem.
The complement of a regular language is regular.
We prove this using Kleene’s Theorem.
3 / 22
Closure properties of regular languages
Theorem.
The complement of a regular language is regular.
Proof. (outline)
Suppose we have a Regular Language.
There must be a regular expression that defines it.
So, by Kleene’s Theorem, there is a Finite Automaton (FA) that defines this language.
We can convert this FA into one that defines the complement of the language. (See
Lecture 7.)
So, by Kleene’s Theorem, there is a regular expression that defines the complement.
4 / 22
Closure properties of regular languages
Theorem.
The union of two regular languages is regular.
Proof.
Suppose L1 and L2 are regular.
By definition of “regular language”,
there exist regular expressions R1 and R2
that describe L1 and L2, respectively.
Then R1 ∪ R2 is a regular expression that describes L1 ∪ L2.
I This uses part 3(iii) of the inductive definition of regular expressions in Lecture 6.
So L1 ∪ L2 is regular.
5 / 22
Closure properties of regular languages
Theorem.
The intersection of two regular languages is regular.
We can’t just mimic the proof that regular languages are closed under union, since
there is no ∩ operation on regular expressions.
6 / 22
Closure properties of regular languages
Theorem.
The intersection of two regular languages is regular.
Proof.
Suppose L1 and L2 are regular.
We know that their complements L1 and L2 are regular.
So the union of these, L1 ∪ L2, is therefore regular, by the previous Theorem.
Its complement, L1 ∪ L2, must also be regular.
But L1 ∪ L2 = L1 ∩ L2 = L1 ∩ L2.
So L1 ∩ L2, must also be regular.
7 / 22
Closure properties of regular languages
Exercises
I Prove that the class of regular languages is closed under concatenation.
L1L2 := {xy : x ∈ L1, y ∈ L2}
I Prove that the class of regular languages is closed under symmetric difference.
(You can use the closure results we’ve already proved.)
L14L2 := {strings in L1 but not in L2, or in L2 but not in L1}
I Is the class of regular languages closed under taking subsets?
i.e., is a subset of a regular language necessarily regular?
I Is the class of regular languages closed under taking supersets?
i.e., is a superset of a regular language necessarily regular?
8 / 22
Circuits in Finite Automata
Definition
A circuit is a directed path which starts and ends at the same state.
The length of a circuit is the number of edges in the path.
Observation
Take any Finite Automaton.
Take any string w with has at least as many letters as there are states in that Finite
Automaton.
Then the path taken for input w must contain a circuit.
We can divide w up naturally into three parts, w = xyz , where:
x := the part before the circuit;
y := the part that goes around the circuit;
z := the part after the circuit;
9 / 22
w = a
x
baaa
y
abb
z
If w is accepted,
then so are . . .
a
x
abb
z
a
x
baaa
y
abb
z
a
x
baaa
y
baaa
y
abb
z
. . .
. . .
b
a
a
b
b
a
a a
a
b
a
b
b
a
b
b
a
b
a
a
a
a
b
b
10 / 22
w = ba
y
bb
z
x = ε
If w is accepted,
then so are . . .
bb
z
ba
y
bb
z
ba
y
ba
y
bb
z
. . .
. . .
b
a
a
b
b
a
a a
a
b
a
b
b
a
b
b
a
b
b
11 / 22
Pumping Lemma
Theorem. (Pumping Lemma)
Let L be an infinite regular language, accepted by a FA with N states.
Then for all words w ∈ L with at least N letters,
there exist strings x , y , z , with y 6= ε, such that
I w = xyz
I length(x) + length(y) ≤ N
I for all i ≥ 0, xy iz ∈ L,
i.e.,
xz , xyz , xyyz , . . . , xynz , . . . ∈ L.
Symbolically:
∀w ∈ L : |w | ≥ N ⇒
(
∃x , y , z : (w = xyz)∧(y 6= ε)∧(|x |+|y | ≤ N)∧(∀i ≥ 0 : xy iz ∈ L)
)
12 / 22
Pumping Lemma
Proof.
Take any word w ∈ L with ≥ N letters.
By our earlier Observation on circuits in FAs, the path taken by w must include a
circuit.
Let
x be the letters of w up to the first circuit.
y be the letters corresponding to the circuit.
z be the remaining letters of w .
We have:
I w = xyz by construction.
I Since the circuit exists, y 6= ε.
I length(x) + length(y) ≤ N, since the FA reads xy without repeating any state.
I Since w = xyz ∈ L, and y starts and finishes at endState(x), and z goes from
endState(x) to a Final State, we can repeat y any number of times (or none) and
still we end up at the same Final State.
13 / 22
Pumping Lemma: application
Consequence
Using the Pumping Lemma we can show there are non-regular languages.
Method
Assume L is regular.
Then, by Kleene’s Theorem, it is recognised by some FA.
Let N be the number of states in this FA.
Choose a suitable word w ∈ L, of length ≥ N.
Show that, for any x , y 6= ε, and z such that w = xyz and |xy | ≤ N . . .
. . . there exists i ≥ 0 s.t. xy iz 6∈ L.
Contradiction.
Compare quantifiers above with those in Pumping Lemma
14 / 22
Non-regular languages
HALF-AND-HALF:
L := {anbn : n ≥ 0} = {ε, ab, aabb, aaabbb, . . .}.
Theorem.
L is not regular.
Proof. (by contradiction)
Assume that L is regular.
Let N = # states in an FA for it.
Choose w := adN/2ebdN/2e.
dN/2e letters︷ ︸︸ ︷
aaa · · · · · · · · · · · · aa
dN/2e letters︷ ︸︸ ︷
bbb · · · · · · · · · · · · bb
Observe that |w | ≥ N.
Consider any x , y 6= ε, and z such that w = xyz and |xy | ≤ N.
Think: are xz , xyz , xyyz , . . . , xyNz , . . . all in L?
15 / 22
Non-regular languages
Case 1: y is all a’s.
dN/2e letters︷ ︸︸ ︷
aaa · · · · · · · · ·︸ ︷︷ ︸
y
· · · aa
dN/2e letters︷ ︸︸ ︷
bbb · · · · · · · · · · · · bb
Then xyyz has more a’s than b’s, since y 6= ε.
So xy2z 6∈ L.
Case 2: y is all b’s. aaa · · · · · · · · · · · · aabbb · · · · · · · · ·︸ ︷︷ ︸
y
· · · bb
Then xyyz has more b’s than a’s, since y 6= ε.
So xy2z 6∈ L.
Case 3: y contains an ab. aaa · · · · · · · · · · · · aabbb · · ·︸ ︷︷ ︸
y
· · · · · · · · · bb
Then xyyz has two occurrences of ab. This cannot happen for strings in L. So xy2z 6∈ L.
In every possible case, we have found an i such that xy iz 6∈ L.
This violates the conclusion of the Pumping Lemma.
Contradiction.
16 / 22
Non-regular languages
HALF-AND-HALF:
L := {anbn : n ≥ 0} = {ε, ab, aabb, aaabbb, . . .}.
Theorem.
L is not regular.
Proof. (by contradiction)
Assume that L is regular. Let N = # states in an FA for it.
Choose w = aNbN . [No need for w to be of minimum length.]
Consider any x , y 6= ε, and z such that w = xyz . . .
. . . and |xy | ≤ N. [Previous proof didn’t use |xy | ≤ N. Can it help?]
Think: are xz , xyz , xyyz , . . . , xyNz , . . . all in L?
How many cases now?
17 / 22
Non-regular languages
Just one case: y is all a’s.
N letters︷ ︸︸ ︷
aaa · · · · · · · · ·︸ ︷︷ ︸
y
· · · aa
N letters︷ ︸︸ ︷
bbb · · · · · · · · · · · · bb
Consider xyyz .
N+|y | letters︷ ︸︸ ︷
aaa · · · · · · · · ·︸ ︷︷ ︸
y
· · · · · ·︸ ︷︷ ︸
y
· · · aa
N letters︷ ︸︸ ︷
bbb · · · · · · · · · · · · bb
It has more a’s than b’s, since y 6= ε.
So xy2z 6∈ L.
This violates the conclusion of the Pumping Lemma.
Contradiction.
18 / 22
Non-regular languages
EQUAL := { all words which have an equal number of a’s and b’s }
= {ε, ab, ba, aabb, abab, abba, baba, . . .}
Theorem.
EQUAL is not regular.
Proof. Assume EQUAL is regular.
Observe:
HALF-AND-HALF := {anbn : n ≥ 0} = EQUAL ∩ a∗b∗.
This implies that HALF-AND-HALF is also regular, since the language defined by a∗b∗
is regular, and regular languages are closed under intersection.
But we have just seen that HALF-AND-HALF is non-regular.
This is a contradiction.
So our initial assumption, that EQUAL is regular, is wrong.
Therefore EQUAL is non-regular. 19 / 22
Non-regular languages
PALINDROME := { all the strings which are the same if they are spelt backwards }
= {ε, a, b, aa, bb, aaa, aba, bab, bbb, . . .}
Theorem.
PALINDROME is non-regular.
Proof. (by contradiction)
Assume PALINDROME is regular.
Then there exists a FA with N states which accepts PALINDROME.
Choose w = aNbaN .
N letters︷ ︸︸ ︷
aaa · · · · · · · · · · · · aa b
N letters︷ ︸︸ ︷
aaa · · · · · · · · · · · · aa
20 / 22
Non-regular languages
Consider all strings x , y 6= ε, and z such that
I w = xyz ,
I length(x) + length(y) ≤ N.
N letters︷ ︸︸ ︷
aaa · · · · · · · · ·︸ ︷︷ ︸
y
· · · aa b
N letters︷ ︸︸ ︷
aaa · · · · · · · · · · · · aa
Consider xyyz .
N+|y | letters︷ ︸︸ ︷
aaa · · · · · · · · ·︸ ︷︷ ︸
y
· · · · · ·︸ ︷︷ ︸
y
· · · aa b
N letters︷ ︸︸ ︷
aaa · · · · · · · · · · · · aa
Since y 6= ε, the solitary b in w is more than half-way along xy2z .
So xy2z is not a palindrome.
This contradicts the conclusion of the Pumping Lemma applied to PALINDROME.
So our initial assumption, that PALINDROME is regular, is wrong.
Therefore PALINDROME is not regular.
21 / 22
Revision
{ all languages }
{ regular languages }
Reading: Sipser, Ch. 1.
I closure properties: pp. 58–63.
I Pumping Lemma, non-regular languages: pp. 77–82.
22 / 22