2
$\begingroup$

While learning about the pumping lemma, I came across the following question:

Given the language L is $ a^n(0|1)^* $ with $ c_0 \cdot c_1 = n $, where $ c_0 $ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are 0, 1, a01, aa001, etc...

In regular english: a word with leading as, followed by any amount of either 0 or 1 characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of as.

My initial attempt was the following:

  • Pick w as $ a^p0^p1 $. This obviously holds since $ p \cdot 1 = p $.
  • Split w into xyz as $ x = \epsilon $, $ y = a^p $, $ z = 0^p1 $.
  • Show that $ xy^2z = a^{2p}0^p1 $ does not hold, since $ p \cdot 1 \ne 2p $.

However, the answer key instead opts to introduce two new variables $ m \geq 0 $, $ n \gt 0 $, then splits on $ x = a^m $, $ y = a^n $, $ z = a^{p-n-m}0^p1 $ (splitting the sequence of a into three parts). Then, they too use $ i = 2 $ to show that $ xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1 $, which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $ |xy| \leq p $ condition of the pumping lemma: x is empty and $ |y| = p $. As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually does violate the $ |xy| \leq p $ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?

$\endgroup$
  • $\begingroup$ I'm not sure what you mean by your title. The condition $|xy|\leq p$ doesn't depend on $i$: it's a fact about $x$, $y$ and $p$ only. $\endgroup$ – David Richerby May 20 at 16:06
2
$\begingroup$

Your mistake is in the following step:

  • Split $w$ into $xyz$ as $x = \epsilon$, $y = a^p$, $z = 0^p 1$.

You're not allowed to choose how $w$ splits into $xyz$. You should show that for any way of splitting $w$ into $xyz$ such that $|xy| \leq p$ and $y \neq \epsilon$, there exists $i$ such that $xy^iz \notin L$.

Here is a similar "proof" that the language $01^*$ isn't regular:

  • Pick $w$ as $01^p$.
  • Split $w$ into $xyz$ as $x = \epsilon$, $y = 0$, $z = 1^p$.
  • Show that $xy^2z = 0^21^p$ is not in the language.

The proof of the pumping lemma will choose a different splitting, for example $x = 0$, $y = 1$, $z = 1^{p-1}$.

$\endgroup$
  • $\begingroup$ Oh duh! Can't believe I forgot what is essentially the essence of the entire pumping lemma (showing that there's no way at all to satisfy it). Much love. $\endgroup$ – Peter May 20 at 15:36

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.