A non-regular language satisfying the pumping lemma

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

• 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. Commented Apr 16, 2015 at 7:26
• possible duplicate of How to prove that a language is not regular? Commented Apr 16, 2015 at 7:59
• @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. Commented Apr 16, 2015 at 10:42
• Closely related: Languages that satisfy the pumping lemma but aren't regular? Commented Apr 16, 2015 at 15:11
• 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. Commented Feb 22, 2021 at 15:02

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.

$$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.

• 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? Commented Oct 30, 2022 at 17:45
• You can pump $aaa$ instead. Commented Oct 30, 2022 at 21:34