0
$\begingroup$

Show that the language $L = \{w \mid w \in \{a,b\}^{*}\}$ is not regular by using the following version of Pumping Lemma:

Let $L$ be the language, which has an infinite number of words, then there are words $x,y,z \in \Sigma ^{*}$, so that $|xz| \leq |\Sigma_{k}|$, and each word $xy^{(i)}z, i\geq 0$ is in $L$.

I don't really know how to use it. Could you give me a hint?

$\endgroup$
3
  • $\begingroup$ It is given that the standard variant of the Pumping Lemma is: Let L be the language of the automaton M, which has an infinite number of words, then there are words $x,y,z \epsilon \Sigma^{*}$, so that each word $xy^{(i)}z \epsilon L$. $\endgroup$
    – evinda
    Dec 14 '13 at 15:22
  • $\begingroup$ If we would have the original version of Pumping Lemma,we could take the word 0^{p}10^{p}1,where p is the pumping length.Can we also do this in our case? $\endgroup$
    – evinda
    Dec 14 '13 at 22:14
  • $\begingroup$ There are a few problems with your version of the pumping lemma as formulated in the question. First of all, you want to say that "If $L$ is an infinite regular language, then there are ...". Second, what is $|\Sigma_k|$? Third, in your formulation, $|y|$ could be 0. $\endgroup$ Mar 19 '14 at 20:09
1
$\begingroup$

I presume you mean the following (much) weaker version of the pumping lemma.

Let $L \subseteq \Sigma^*$ be an infinite regular language. Then there are $x, y, z \in \Sigma^*$ with $y \neq \epsilon$ such that for all $i \in {\mathbb N}$, $xy^iz \in L$.

(The proof of this, using the usual version of the pumping lemma, is easy. Let $p$ be the pumping length, take a word $\sigma \in L$ with $|\sigma| \geq p$. Such a word must exist, because $L$ is infinite. By the usual version of the pumping lemma, there are $x, y, z \in \Sigma^*$ with $\sigma = x y z$, $y \neq \epsilon$, $|xy| \leq p$ and $xy^iz \in L$ for all $i \in {\mathbb N}$.

Note that it really is a much weaker formulation. The pumping lemma says that every sufficiently long word in $L$ can be pumped; this version only states that there exists a word in $L$ that can be pumped.)

However, for your language $L = \{ \sigma^2 \mid \sigma \in \{a,b\}^* \}$, although not regular, the claim of the weaker version of the pumping lemma does hold. You could take, for instance $x = y = z = aa$. Then $xy^iz = a^{2i + 4} = a^{i+2} a^{i+2} \in L$, for all $i \in \mathbb N$. So, you can't use this to show that $L$ is not regular.

Of course, as you noted, you can apply the usual version of the pumping lemma to $0^p10^p1$ to show that $L$ is not regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.