I got a problem to solve, which is to demostrate that the language $L$, given by:

$L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$

  1. Satisfies the pumping lemma.
  2. Is not regular.

For the question 1. I think it would suffice to demonstrate that for all $w \in L$, $w$ can be decomposed in the form $\alpha \beta \gamma$, where $|\beta| \neq 0$, and that every string $\alpha \beta^m \gamma \in L$, where $m \geq 0$, but after that I have no clear what I have to do, because I start thinking about cases, what if I have a string $w \in \{ab^nc^n\mid n \geq 0\}$... I should decompose it the way $\alpha = \epsilon, \beta = a$ and $\gamma = \text{the rest of the string}$ (because if we use $w = ab^0c^0 = a$, $\beta$ will have to be $a$, because we know that $\beta \neq \epsilon$), but in this case $\alpha \beta^m$ may not be in $L$, for example, if we choose $m = 0, \alpha \beta^m \gamma$ won't be in $L$, so I don't know what I'm doing wrong... perhaps I'm making mistakes in several steps.

Now, for the question 2. I don't even have an idea on how to start, if someone would help me I would really appreciate it

  • $\begingroup$ Perhaps you would care to define $L$ properly. What does $2$ mean in its definition? If it is supposed to mean that $k \geq 2$, then I think that the pumping lemma does work. $\endgroup$ Apr 16, 2015 at 7:26
  • $\begingroup$ possible duplicate of How to prove that a language is not regular? $\endgroup$ Apr 16, 2015 at 7:59
  • $\begingroup$ @YuvalFilmus I edited the question as the definition of $L$ did not make sense. I did not use the definition of the existing answer (which I had not read). But I do not think it makes a difference. Hope you agree. $\endgroup$
    – babou
    Apr 16, 2015 at 10:42
  • 2
    $\begingroup$ Closely related: Languages that satisfy the pumping lemma but aren't regular? $\endgroup$ Apr 16, 2015 at 15:11
  • $\begingroup$ I just want to point out a mistake in the edited version of the question (as opposed to the correct answer by Yuval). The right side of the union cannot be $\{a^kw\mid k\geq 2\wedge w\in\Sigma^*\}$ as the resulting $L$ will then not contain words that do not start with an $a$. However, if you pump $ab^nc^n$, the only choice to pump is the $a$, which means that also $b^nc^n$ must be in $L$. Hence, the way this is set up won't work -- with Yuval's version it does work, of course. $\endgroup$ Feb 22, 2021 at 15:02

1 Answer 1


You are not supplying the definition of $L$, so here is one definition which works:

$$ L = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 1 \text{ and } w \in \Sigma^* \text{ doesn't start with $a$} \}. $$

Choose a pumping length of $3$. A word $ab^nc^n \in L$ can be pumped by pumping the $a$ part. A word $aabw$ or $aacw$ can be pumped by pumping the $aa$ part. A word $aaaw$ can be pumped by pumping the first $a$. Finally, a word $bw$ or $cw$ can be pumped by pumping the $b$ part or $c$ part.

Your definition seems to be

$$ L' = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 2 \text{ and } w \in \Sigma^* \}, $$

but for this language the pumping lemma does work. Indeed, apply it to $ab^nc^n \in L'$ for large enough $n$. Then $ab^nc^n = xyz$ so that $|y| \geq 1$ and $xy^iz \in L'$ for all $i \geq 0$. Considering the case $i = 2$, we see that $y = a$ necessarily. But then, taking $i = 0$ we get $xz = b^nc^n \notin L'$.

Perhaps the exercise meant you to use the version of the pumping lemma in which $i \geq 1$ instead of $i \geq 0$.

We can show that $L$ is not regular in many ways:

  1. Use one of the many general versions of the pumping lemma which can force the $b^nc^n$ to be pumped. For example, the general version on Wikipedia states that there exists $p$ such that any word $uwv \in L$ with $|w| \geq p$ can be partitioned as $w = xyz$ so that $|xy| \leq p$, $|y| \geq 1$ and $uxy^iz \in L$ for all $i \geq 0$. Choose $u = a$, $w = b^nc^n$ for $n \geq p$ and $v = \epsilon$, and follow the usual argument.

  2. If $L$ were regular then $L \cap ab\Sigma^* = \{ ab^nc^n : n \geq 1 \}$ would also be regular, and you can prove that it isn't using the usual pumping lemma.

  3. Use the Myhill–Nerode criterion. The words $ab^n$ are pairwise inequivalent, and so $L$ is not regular.

  • $\begingroup$ Are you saying that given the word $aaab\in L$, which is of the form $aaw$, you would pump it by pumping the prefix $aa$? Then $(aa)^iab$ is $ab$ for $i=0$ and $ab\not\in L$. Is this a mistake in the answer or am I missing something? $\endgroup$
    – mimo31
    Oct 30, 2022 at 17:45
  • $\begingroup$ You can pump $aaa$ instead. $\endgroup$ Oct 30, 2022 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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