Consider this example (taken from this document: Showing that language is not regular):$$L = \{1^n \mid n\text{ 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?
Why is this example a regular language?
formal languages;regular languages;proof techniques
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)*. 