1
$\begingroup$

This question already has an answer here:

Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular

I'd like to check if my proof for this is correct.

Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+1 \geq m$ and $1\leq |a^m| \leq m$. Write $w=xyz$ where $x=\varepsilon$, $y=a^m$ and $z=b^{m+1}$. We have $$xy^3z= \varepsilon(a^m)^3b^{m+1} = a^{3m}b^{m+1} \not\in L\,,$$ since $3m > m+1$ for any positive integer $m$. Thus by the contrapositive of the Pumping Lemma we can conclude that $L$ is not regular. $\square$


Although we normally close "check my work questions", this question illustrates a very common mistake with the pumping lemma, so is intended as a reference question.

$\endgroup$

marked as duplicate by Gilles Oct 6 '18 at 21:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I edited the proof slightly to turn this into a reference question because you've made a common and instructive mistake. You also did some slightly strange stuff observing that $\varepsilon=a^0b^0\in L$ which is true but not relevant. Nothing in the pumping lemma requires that $x\in L$, so I removed that part. $\endgroup$ – David Richerby Oct 6 '18 at 20:55
  • $\begingroup$ Doh! I did the exact same thing with a different "is my pumping lemma proof correct?" question three years ago, and wrote an almost identical answer! So this should be closed as a duplicate. $\endgroup$ – David Richerby Oct 6 '18 at 20:59
0
$\begingroup$

No, this proof is not correct.

To prove that a language is non-regular using the pumping lemma, you need to show that:

  1. for all $m>0$, there is a string $w\in L$ of length at least $m$ such that
  2. for all ways of writing $w=xyz$ with $|y|\geq 1$,
  3. there is some $i\geq 0$ such that $xy^iz\notin L$.

You have shown that some way of writing $w=xyz$ makes part 3 true, but that is not enough.

To understand why, it's helpful to consider why the pumping lemma is true. The point is that, if a language is regular, it is accepted by a DFA and that DFA has some number $n$ of states. That means that, if it reads a string $w$ of length more than $n$ then, by the pigeonhole principle, it must enter some state $q$ twice (or more). Then we can set $w=xyz$ where

  • $x$ is what is read before entering $q$ for the first time ($x=\varepsilon$ if $q$ is the initial state);
  • $y$ is what is read after the character that causes the first entry to $q$ up to, but not including, the character that causes the second entry to $q$ (so $y$ contains at least one character, i.e., $|y|\geq 1$);
  • $z$ is the rest of the string.

Now the point is that the string $xy^iz$ causes the DFA to go around the loop from $q$ to $q$ $i$ times, then carry on to an accepting state by reading $z$, so every string $xy^iz$ must also be accepted. However, the specific partition of $w$ into $x$, $y$ and $z$ depends on which automaton you're considering. To show that no automaton accepts the language, you need to show that every possible automaton fails, which means you need to show that all possible partitions $w=xyz$ fail.

$\endgroup$

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