A non-regular language satisfying the pumping lemma

Question

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

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.