Why is this example a regular language?

Problem Detail: 

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?

Asked By : Amumu

Answered By : Kaveh

1. 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.

2. 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.

3. The language is indeed regular, it is (11)*.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1706