**CS 341 Automata Theory**
**TA: Tazeen Siddiqui**
**Pumping Lemma for Regular Languages**
**What is the pumping lemma for regular languages?**
If L is a regular language then
there exists N ≥ 1 such that
for all strings w in L, where |w| ≥ N,
there exist x ,y, z such that w = xyz
& |xy| ≤ N
& y ≠ epsilon
& for all q, xy^{q}z is in L
**But what does that mean??**
If L is a regular language then all strings in it, of length greater than or equal to N, can be divided into three parts. Such that if you either remove or repeat the middle part any number of times, the resulting string will still be in L.
**Hmm, an example would be nice…**
L = a(bb)*a
If you take any string of length greater than or equal to 4 (that’s the N in this example), it can be divided into three parts such that the middle part (or the part that comes from the loop) can be removed or repeated any number of times and the resulting string would still be in the language.
For example, let the string be abba. It can be divided into three parts xyz such that x = a, y = bb, and z = a.
Now for all q, xy^{q}z is in L.
If q is 0 (called pumping down, since in effect you’re removing the loop), xy^{q}z = aa, which is in L.
If q = 2 (if q ≥ 2, it’s called pumping up, since you’re increasing the number of times you take the loop), xy^{q}z = a(bb)^{2}a = abbbba, which is still in the language.
(Note that N is a constant, in this case 4. When you’ll be using the pumping lemma, N will be an unknown constant. There’s a difference between the language a^{N}b^{N} and the string a^{N}b^{N}. The N in a language definition is just like any other variable. When you use it to pick a string for the pumping lemma, it’s the pumping constant.)
**What if L is a finite language?**
If L is a finite language, it is regular, but you cannot pump it to get other strings that are in the language. This is because the finite state machine doesn’t have any loops in it. If it had a loop then it could accept an infinite number of strings. The pumping lemma is still correct though, it’s just that if L is a finite language then it doesn’t have any strings of length greater than or equal to N.
**Ok, so how can I use this?**
You *cannot* use this to prove that a language is regular because then you would have to show that the pumping lemma works for all q.
You *can* use this to prove that a language is not regular by showing that for all possible ways of breaking up the string into three parts there is at least one q for which the resulting string is not in L.
**Show me how.**
**Example 1:**
L = {mm^{R} : m is in {a, b}*}
**Detailed answer:**
Pick a string from L in terms of the pumping lemma constant N.
w = xyz = a^{N}b^{N}b^{N}a^{N}
Given that |xy| ≤ N from the pumping lemma theorem, y must be some number of a’s.
y = a^{p}
Given that y ≠ epsilon, p > 0.
Since x comes before y, it must also be some number of a’s.
x = a^{t}
Since w = xyz, z must be everything else.
z = a^{N-(p+t)}b^{N}b^{N}a^{N}
In this example, it doesn’t matter if you pump up or pump down. Just pick one.
Pumping up, q = 2.
xy^{2}z = a^{t}(a^{p})^{2}a^{N-(p+t)}b^{N}b^{N}a^{N} = a^{t} a^{p} a^{p} a^{N-(p+t)} b^{N} b^{N} a^{N} = a^{N+p }b^{N }b^{N} a^{N}
Given that p > 0, the number of a’s at the start of the string are not equal to the number of a’s at the end of the string, xy^{2}z is not in L, so L is not regular.
**Shorter answer** (all you have to do in the exam. However, if you can’t do the longer answer, it’s a sign you don’t understand something and may get the short answer wrong. If you don’t understand something, ask):
w = a^{N}b^{N}b^{N}a^{N}
y = a^{p}
Pumping up, q = 2.
More a’s at the start than at the end, xy^{2}z is not in L. Therefore L is not regular.
**Note:**
If possible pick a w such that the first N characters are from the same symbol, such as a^{N}. Since |xy| ≤ N, picking a string in such a way ensures that there is only one possibility for y. Sometimes it’s not possible to do so.
**Example 2:**
L = { a^{R} b^{M} c^{M}: R, M > 0}
w = a b^{N} c^{N} (Note you don’t want to pick a^{N} b^{N} c^{N}, because then you’ll be pumping in the a’s and the resulting string will still be in L)
case 1: y = a (x can be epsilon)
Pump down, q = 0.
No a at the start of the start of the string, xy^{0}z is not in L.
case 2: y = b^{p}
Pump up, q = 3. (could’ve picked any value q ≥ 2 for pumping up)
More b’s than c’s. xy^{3}z is not in L.
case 3: y = a b^{t}
Pump up, q = 2. Out of order a’s and b’s. xy^{2}z is not in L.
In all possible cases for y, pumping results in strings that are not in L. Therefore, L is not regular.
**Example 3:**
L = {a^{R} b^{M} c^{M} : R, M ≥ 0 }
w = b^{N} c^{N}
y = b^{P}
Pump down, q = 0.
Fewer b’s than c’s. Not in L. L is not regular.
**Example 4:**
L = {a^{i} b^{j} c^{k} : i = 1 => j > k}
You can rewrite L as:
L = {a^{i} b^{j} c^{k} : i ≠ 1 or j > k}
L complement = {a^{i} b^{j} c^{k} : i = 1 and j ≤ k}
w = a b^{N} c^{N}
case 1: y = a, pump up, more than 1 a. Not in L complement
case 2: y = b^{p}, pump up, more b’s than c’s. Not in L complement.
case 3: y = a b^{t}, pump up. Out of order a’s and b’s. Not in L complement.
For all possible cases for y, pumping results in strings that are not in L complement. Therefore L complement is not regular.
Since regular languages are closed under complementation. If L was regular then its complement would also be regular. Since L complement is not regular, L must also be not regular. |