Problem Detail: Consider this example (taken from this document: Showing that language is not regular): $$L = {1^n mid ntext{ is even}} $$ According to the Pumping Lemma, a language $L$ is regular if :
- $y ne ε$
- $|xy| lt n$
- $forall k in N, xy^kz in L$
In the above example, $n$ must be even. Suppose we have $n = 4$, we can express: $$xy^kz$$ such that: $x = 1$, $z = 1$, and with $k = 2$, we have $y^k = y^2 = 11$, so we get the string $1111$. However, since all $k$ must be satisfied, if $k = 1$, the string is $111$, it does not belong to $L$. Yet, I was told that the above example is a regular language. How can it be?
Asked By : Amumu
Answered By : Kaveh
- Pumping lemma is not a sufficient condition for being regular, it is only a necessarily condition. Satisfying it does not imply that the language is regular.
- In the pumping lemma, some parameters are chosen adversarily, i.e. you don’t have control over them. If a language is regular then pumping lemma says that “for a long enough string in the language there is a partition s.t. …”. To show that a language is not regular you should show that for all ways of partitioning the conditions will not hold. Your argument does rule out $y=11$ for example, you are only talking about a particular way of partitioning and that does not imply anything.
- The language is indeed regular, it is (11)*.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1706
