patternMinor
Pumping lemma: if you can keep pumping, what does this tell you?
Viewed 0 times
thiscanyouwhatkeeptellpumpinglemmadoes
Problem
Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation, do you have to "throw out" the lemma so to speak? I am under the impression that the answer is yes, but I'm just not sure.
Solution
If you are not sure, it is probably because you want to know why. This question is frequent among students in computer science that are learning the pumping lemma for the first time and it is the cause of a lot of errors.
Logic
The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but it is analog for the context-free version of the lemma. The statement that has been proved is the following:
$$1)\ L\text{ is a regular language}\implies L\text{ complies with the pumping lemma}$$
This is all we know. Notice that this implication is in one direction. In other words we can't conclude:
$$2)\ L\text{ complies with the pumping lemma}\implies L\text{ is a regular language}$$
It is a common mistake to invert the propositions in the first implication and expect to obtain a logically equivalent statement (you can't use the second statement!).
When we use the pumping lemma we are actually using the contrapositive of the first implication:
$$3)\ L\text{ doesn't complies with the pumping lemma} \implies L\text{ is not regular}$$
The first and the third statements are logically equivalent. This is why we search for a contradiction when trying to force $L$ to fulfill the pumping lemma. If $L$ doesn't comply with the lemma then we are sure that $L$ is not regular. If you were paying attention you could have noticed that we can't prove that $L$ is regular using the pumping lemma. If you want to prove that $L$ is a regular language you should find a regular expression, NFA or a DFA (or even a regular grammar) that denotes $L$.
Inside the pumping lemma
Another big source of error is the incorrect interpretation of the lemma. Every word in the lemma is very important:
Pumping lemma: If $L$ is regular then there exists a constant $N\in \mathbb{N}$ such that for all $\sigma$ in $L$ with $|\sigma|\geq N$ there exists a decomposition $\sigma=\alpha\beta\gamma$ such that:
a) $|\alpha\beta|\leq N$
b) $\beta \neq \epsilon$
c) $\alpha\beta^i\gamma \in L\ \forall i \in \mathbb{N}_0$
Common mistakes
1) My word $\sigma$ complies with the pumping lemma so $L$ must be regular:
This is wrong for so many reasons. First, we can't conclude that $L$ is regular using the pumping lemma (see the Logic section). Second, a lot of words can comply the three conditions but the lemma clearly state that all $\sigma\in L$ with $|\sigma|\geq N$ should comply. So good luck trying with another word!
2) If I choose this particular $\alpha$, $\beta$ and $\gamma$ I find a contradiction!:
This is wrong too. The lemma states that there exists a decomposition(at least one) that fulfill the lemma. So if you choose one and it doesn't meet the three conditions it doesn't say too much... Now you have to try with all the remaining possible decompositions! You will find a contradiction when you prove that is impossible to find such a decomposition.
3) If I choose the word $\sigma=\epsilon$ I find a contradiction!:
This is wrong for two reasons. First, $N>0$. Second, the lemma states that there exists a constant $N$. If you choose $N=0$ (wrong by definition) or $N=1$, $N=2$, etc and you find a contradiction it is okay. Now you have to try all the remaining integer $N$! This is the reason why you should never try to choose a specific constant $N$ and why you should use a generic constant instead.
4) I tried a lot of words and all of them comply with the pumping lemma... what do I do?:
At this point you have two options. You can suspect that $L$ is regular and try to find a regular expression(or NFA, DFA, regular grammar...) that denotes $L$. If you suspect that $L$ is not regular then maybe it is time to use closure properties to simplify the problem or you can continue your epic quest of proving that $L$ is not regular by trying others words.
These are all the tips I have for now. If I can remember some more in the future I will add them here.
Logic
The reason is very simple. It is because of logic. I will explain it considering the pumping lemma for the regular languages but it is analog for the context-free version of the lemma. The statement that has been proved is the following:
$$1)\ L\text{ is a regular language}\implies L\text{ complies with the pumping lemma}$$
This is all we know. Notice that this implication is in one direction. In other words we can't conclude:
$$2)\ L\text{ complies with the pumping lemma}\implies L\text{ is a regular language}$$
It is a common mistake to invert the propositions in the first implication and expect to obtain a logically equivalent statement (you can't use the second statement!).
When we use the pumping lemma we are actually using the contrapositive of the first implication:
$$3)\ L\text{ doesn't complies with the pumping lemma} \implies L\text{ is not regular}$$
The first and the third statements are logically equivalent. This is why we search for a contradiction when trying to force $L$ to fulfill the pumping lemma. If $L$ doesn't comply with the lemma then we are sure that $L$ is not regular. If you were paying attention you could have noticed that we can't prove that $L$ is regular using the pumping lemma. If you want to prove that $L$ is a regular language you should find a regular expression, NFA or a DFA (or even a regular grammar) that denotes $L$.
Inside the pumping lemma
Another big source of error is the incorrect interpretation of the lemma. Every word in the lemma is very important:
Pumping lemma: If $L$ is regular then there exists a constant $N\in \mathbb{N}$ such that for all $\sigma$ in $L$ with $|\sigma|\geq N$ there exists a decomposition $\sigma=\alpha\beta\gamma$ such that:
a) $|\alpha\beta|\leq N$
b) $\beta \neq \epsilon$
c) $\alpha\beta^i\gamma \in L\ \forall i \in \mathbb{N}_0$
Common mistakes
1) My word $\sigma$ complies with the pumping lemma so $L$ must be regular:
This is wrong for so many reasons. First, we can't conclude that $L$ is regular using the pumping lemma (see the Logic section). Second, a lot of words can comply the three conditions but the lemma clearly state that all $\sigma\in L$ with $|\sigma|\geq N$ should comply. So good luck trying with another word!
2) If I choose this particular $\alpha$, $\beta$ and $\gamma$ I find a contradiction!:
This is wrong too. The lemma states that there exists a decomposition(at least one) that fulfill the lemma. So if you choose one and it doesn't meet the three conditions it doesn't say too much... Now you have to try with all the remaining possible decompositions! You will find a contradiction when you prove that is impossible to find such a decomposition.
3) If I choose the word $\sigma=\epsilon$ I find a contradiction!:
This is wrong for two reasons. First, $N>0$. Second, the lemma states that there exists a constant $N$. If you choose $N=0$ (wrong by definition) or $N=1$, $N=2$, etc and you find a contradiction it is okay. Now you have to try all the remaining integer $N$! This is the reason why you should never try to choose a specific constant $N$ and why you should use a generic constant instead.
4) I tried a lot of words and all of them comply with the pumping lemma... what do I do?:
At this point you have two options. You can suspect that $L$ is regular and try to find a regular expression(or NFA, DFA, regular grammar...) that denotes $L$. If you suspect that $L$ is not regular then maybe it is time to use closure properties to simplify the problem or you can continue your epic quest of proving that $L$ is not regular by trying others words.
These are all the tips I have for now. If I can remember some more in the future I will add them here.
Context
StackExchange Computer Science Q#50559, answer score: 6
Revisions (0)
No revisions yet.