The Pumping Lemma and Closure Properties: Mridul Aanjaneya
The Pumping Lemma and Closure Properties: Mridul Aanjaneya
The Pumping Lemma and Closure Properties: Mridul Aanjaneya
Mridul Aanjaneya
Stanford University
July 5, 2012
Question
Is a given regular language L infinite?
x z
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.
Question
Prove that the language L = {0k 1k | k ≥ 1} is not regular.
Question
Prove that the language L = {ww | w ∈ {0,1}∗ } is not regular.
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.
Question
2
Prove that the language L = {1k | k ≥ 0} is not regular.
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.
Question
Prove that the language L = {0i 1j | i > j} is not regular.
Question
Prove that the language L = {1p | where p is prime} is not regular.
Question
Prove that the language L = {1p | where p is prime} is not regular.
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
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
ER = (01∗ + 10∗ )R
= (01∗ )R + (10∗ )R
= (1∗ )R 0R + (0∗ )R 1R
= (1R ∗ )0R + (0R ∗ )1R
= (1∗ )0 + (0∗ )1