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

2k Views Asked by At

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?

1

There are 1 best solutions below

3
On

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?