0

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?

Michael Albanese
  • 99,526
evinda
  • 7,823
  • 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$. – evinda Dec 14 '13 at 15:22
  • 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? – evinda Dec 14 '13 at 22:14
  • 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. – Magdiragdag Mar 19 '14 at 20:09

1 Answers1

1

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.

Magdiragdag
  • 15,049