The Pumping Lemma and Closure Properties: Mridul Aanjaneya

Download as pdf or txt
Download as pdf or txt
You are on page 1of 27

The Pumping Lemma and Closure Properties

Mridul Aanjaneya

Stanford University

July 5, 2012

Mridul Aanjaneya Automata Theory 1/ 27


Tentative Schedule

• HW #1: Out (07/03), Due (07/11)


• HW #2: Out (07/10), Due (07/18)
• HW #3: Out (07/17), Due (07/25)
• Midterm: 07/31 (in class)
• HW #4: Out (07/31), Due (08/08)
• Tentative grades out by 08/12.
• Final: 08/18 (?)

Mridul Aanjaneya Automata Theory 2/ 27


The Infiniteness Problem

Question
Is a given regular language L infinite?

• Start with a DFA for the language.


• Key idea: If the DFA has n states, and the language contains
any string of length n or more, then the language is infinite.
• Otherwise, the language is surely finite.
Limited to strings of length n or less.

Mridul Aanjaneya Automata Theory 3/ 27


Proof of Key Idea

• If an n-state DFA accepts a string w of length n or more, then


there must be a state that appears twice on the path labeled
w from the start state to a final state.
Note: Pigeonhole principle! ^
¨
• Because there are at least n + 1 states along the path.

x z

• Since y is not ε, we see an infinite number of strings in L of


the form xyi z for all i ≥ 0.

Mridul Aanjaneya Automata Theory 4/ 27


The Pumping Lemma

Theorem
For every regular language L, there is an integer n such that for
every string w ∈ L of length ≥ n, we can write w = xyz such that:

• |xy | ≤ n.
• |y | > 0.
• For all i ≥ 0, xy i z is in L.

Mridul Aanjaneya Automata Theory 5/ 27


The Pumping Lemma: Examples

Question
Prove that the language L = {0k 1k | k ≥ 1} is not regular.

• Proof by contradiction. Suppose it were, and let a DFA with n


states accept all strings in L.
• Choose the string w = 0n 1n . We can write w = xyz where x
and y consist of 0’s, and y 6= ε.
• But then xyyz would be in L, and this string has more 0’s
than 1’s!
• Choice of the proper string is very important!
Example: w = (01)n does not work!
• Same argument as above also works for L = {w | w has equal
number of 0’s and 1’s.}

Mridul Aanjaneya Automata Theory 6/ 27


The Pumping Lemma: Examples

Question
Prove that the language L = {ww | w ∈ {0,1}∗ } is not regular.

Mridul Aanjaneya Automata Theory 7/ 27


The Pumping Lemma: Examples

Question
Prove that the language L = {ww | w ∈ {0,1}∗ } is not regular.

• Suppose it were, and let a DFA with n states accept all strings
in L.
• Choose the string w = 0n 10n 1. We can write w = xyz where
x and y consist of 0’s, and y 6= ε.
• But then xyyz would be in L!
• Note that the string w = 0n 0n does not work.

Mridul Aanjaneya Automata Theory 8/ 27


The Pumping Lemma: Examples

Question
2
Prove that the language L = {1k | k ≥ 0} is not regular.

Mridul Aanjaneya Automata Theory 9/ 27


The Pumping Lemma: Examples

Question
2
Prove that the language L = {1k | k ≥ 0} is not regular.

• Suppose it were, and let a DFA with n states accept all strings
in L.
2
• Choose the string w = 1n . We can write w = xyz. Consider
the string s = xyyz.
• We know that |xy | ≤ n and thus |y | ≤ n. So no. of 1’s in
xyyz is n2 +n < n2 +2n+1!
• The parameter n is often called the pumping length.

Mridul Aanjaneya Automata Theory 10/ 27


The Pumping Lemma: Examples

Question
Prove that the language L = {0i 1j | i > j} is not regular.

Mridul Aanjaneya Automata Theory 11/ 27


The Pumping Lemma: Examples

• Sometimes pumping down is useful as well!


Question
Prove that the language L = {0i 1j | i > j} is not regular.

• Let n be the pumping length, i.e., suppose there exists a DFA


with n states that accepts all strings in L.
• Choose the string w = 0n+1 1n . We can write w = xyz where
x and y consist of 0’s, and y 6= ε.
• The pumping lemma states that all strings xy i z ∈ L, even for
i = 0!
• The string w = xz cannot have more 0’s than 1’s.

Mridul Aanjaneya Automata Theory 12/ 27


The Pumping Lemma: Examples

Question
Prove that the language L = {1p | where p is prime} is not regular.

Mridul Aanjaneya Automata Theory 13/ 27


The Pumping Lemma: Examples

Question
Prove that the language L = {1p | where p is prime} is not regular.

• Consider some primt q ≥ n + 2, where n is the pumping


length.
• Choose the string w = 1q . We can write w = xyz such that y
6= ε and |xy | ≤ n.
• Let |y | = m. Then |xz| = q − m. Consider the string s =
xyq−m z which is in L by the pumping lemma.
• |xyq−m z| = |xz| + (q−m)|y| = q−m + (q−m)m =
(m+1)(q−m).
• Note that m+1 > 1, as y 6= ε.
• Also note that q ≥ n + 2, and so q − m > 1.

Mridul Aanjaneya Automata Theory 14/ 27


Closure Properties

• A closure property of a language class says that given


languages in the class, an operator (e.g., union) produces
another language in the same class.
• Example: We saw that regular languages are closed under
union, concatenation and Kleene closure (star) operations.
• We will see more examples: intersection, difference, reversal,
homomorphism, inverse homomorphism.

Mridul Aanjaneya Automata Theory 15/ 27


Closure Properties: Intersection

• Construct the product DFA from DFA’s for L and M.


• Let these DFA’s have sets of states Q and R respectively.
• Product DFA has set of states Q×R.
i.e., pairs [q,r] with q ∈ Q and r ∈ Q.
• Start state = [q0 ,r0 ] (the start states of the DFA for L and M).
• Transitions: δ([q,r],a) = [δL (q,a),δM (r,a)].
δL , δM are the transition functions for the DFA’s of L and M.
i.e., we simulate the two DFA’s in the two state components of
the product DFA.
• Make final states be pairs consisting of final states of both
DFA’s of L and M.

Mridul Aanjaneya Automata Theory 16/ 27


Product DFA: Example
0 1 0

1 0
A B C D
0,1 1

[A,C]
0 [A,D]

1 1 1
0
0
[B,C] [B,D]

1
Mridul Aanjaneya Automata Theory 17/ 27
Closure Properties: Difference

• If L and M are regular, then so is L − M = strings in L but


not in M.
• Proof: Let A and B be DFA’s whose languages are L and M.
• Construct the product DFA C of A and B.
• Make the final states of C be the pairs where A-state is final
but B-state is not.

Mridul Aanjaneya Automata Theory 18/ 27


Difference: Example
0 1 0

1 0
A B C D
0,1 1

[A,C]
0 [A,D]

1 1 1
0
0
[B,C] [B,D]

1
Mridul Aanjaneya Automata Theory 19/ 27
Closure Properties: Containment

• If L and M are regular, then so is L − M = strings in L but


not in M.
• Proof: Let A and B be DFA’s whose languages are L and M.
• Construct the product DFA C of A and B.
• Make the final states of C be the pairs where A-state is final
but B-state is not.
• Note: Can also be used to test containment.
If L − M = ∅, then L ⊆ M.
How did we test if the language of a DFA is empty?

Mridul Aanjaneya Automata Theory 20/ 27


Closure Properties: Complement

• The complement of a language L is Σ∗ − L.


• Since Σ∗ is regular, the complement is always regular.

Mridul Aanjaneya Automata Theory 21/ 27


Closure Properties: Reversal

• Given language L, LR has all strings whose reversal is in L.


• Example: L = {0, 01, 100};
LR = {0, 10, 001}
• Proof: Let E be a regular expression for L.
• We show how to reverse E, to provide a regular expression ER
for LR .

Mridul Aanjaneya Automata Theory 22/ 27


Reversal of a Regular Expression

• Basis: If E is a symbol a, ε, or ∅, then ER = E.


• Induction: If E is:
F + G, then ER = FR + GR
FG, then ER = GR FR
F∗ , then ER = (FR )∗

Mridul Aanjaneya Automata Theory 23/ 27


Reversal of a RE: Example

• Let E = 01∗ + 10∗ .

ER = (01∗ + 10∗ )R
= (01∗ )R + (10∗ )R
= (1∗ )R 0R + (0∗ )R 1R
= (1R ∗ )0R + (0R ∗ )1R
= (1∗ )0 + (0∗ )1

Mridul Aanjaneya Automata Theory 24/ 27


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 a2 . . .an )=h(a1 )h(a2 ). . .h(an ).
• Example: h(01010) = ababab.

Mridul Aanjaneya Automata Theory 25/ 27


Closure Properties: Homomorphism

• If L is regular, and h is a homomorphism on its alphabet, then


h(L) = {h(w) | w ∈ L} is also regular.
• Proof: Let E be a regular expression for L.
• Apply h to each symbol in E.
• Language of resulting RE is h(L).

Mridul Aanjaneya Automata Theory 26/ 27


Closure under Homomorphism: Example

• Let h(0) = ab, h(1) = ε.


• Let L be the language of a regular expression 01∗ + 10∗ .
• Then h(L) is the language of regular expression abε∗ + ε(ab)∗ .
• Note: abε∗ + ε(ab)∗ = ab + (ab)∗ = (ab)∗ .

Mridul Aanjaneya Automata Theory 27/ 27

You might also like