snippetModerate
Why is this example a regular language?
Viewed 0 times
thiswhyexampleregularlanguage
Problem
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 :
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?
$$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?
Solution
-
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)*.
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)*.
Context
StackExchange Computer Science Q#1706, answer score: 11
Revisions (0)
No revisions yet.