# a^m b^n c^n prove it's not regular/pumping lemma

How to prove that $$L = \{a^mb^nc^n \mid n, m \geq 0\}$$ is not regular by the pumping lemma

My attempt:

1. Let's suppose $$L$$ is regular.
2. There exists a pumping constant p, and we choose $$w = a^pb^pc^p$$
3. We look into all decompositions of $$w$$ into $$xyz$$ such that $$|xy| \leq p$$ and $$|y|\geq 1$$ and that: $$x = a^\alpha, y = a^\beta, z = a^{p-\alpha - \beta}b^pc^p$$
4. We choose an $$i$$ such that $$xy^iz \in L$$. We have $$xy^iz = a^{i \beta+ p -\beta}b^pc^p$$

Case 1: $$n = m$$

$$xy^iz \in L \iff i \beta+ p -\beta = p \iff i = 1$$. We choose $$i = 2$$

Case 2: $$n \neq m$$

$$xy^iz \in L \iff i \beta+ p -\beta \neq p \iff i \neq 1$$. We choose $$i = 2$$

In both cases, we found an $$i$$ that by subsituting it, we get $$L^\complement$$, therefore, $$L$$ is not regular by contradiction.

Is this is a correct solution?

• If $xy^iz = a^{i \beta+ p -\beta}b^pc^p$, then $xy^iz \in L$, so your step 4 does not make sense. Commented Mar 5, 2022 at 10:00
• you re right, exactly right, I should have asked the completion of proof from there
– Papa
Commented Mar 5, 2022 at 10:16
• @J.-E.Pin the problem that I have is that I don't know how to approach this structure $a^mb^nc^n$, I can for $a^nb^n$ and so on
– Papa
Commented Mar 5, 2022 at 10:52
• I have updated my solution if you can correct it if possibel.
– Papa
Commented Mar 5, 2022 at 11:27
• It may help to remember that $\{a^m b^n\}$ and $\{a^m b^n c^p\}$ are regular languages, so you should target what makes this language different: that the number of $b$s and $c$s must be the same. Commented Mar 5, 2022 at 12:19

Hint. You can use the fact that regular languages are closed under intersection. Suppose that $$L$$ is regular. Then so is $$T = L \cap b^*c^*$$. Can you compute $$T$$ and show that it is not regular?
• Why $T$ is regular when it is intersected with a non-regular one?