2
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ If $xy^iz = a^{i \beta+ p -\beta}b^pc^p$, then $xy^iz \in L$, so your step 4 does not make sense. $\endgroup$
    – J.-E. Pin
    Commented Mar 5, 2022 at 10:00
  • $\begingroup$ you re right, exactly right, I should have asked the completion of proof from there $\endgroup$
    – Papa
    Commented Mar 5, 2022 at 10:16
  • $\begingroup$ @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 $\endgroup$
    – Papa
    Commented Mar 5, 2022 at 10:52
  • $\begingroup$ I have updated my solution if you can correct it if possibel. $\endgroup$
    – Papa
    Commented Mar 5, 2022 at 11:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – TomKern
    Commented Mar 5, 2022 at 12:19

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Why $T$ is regular when it is intersected with a non-regular one? $\endgroup$
    – Papa
    Commented Mar 5, 2022 at 20:00
  • $\begingroup$ Do you understand rhe meaning of "Suppose that"? $\endgroup$
    – J.-E. Pin
    Commented Mar 5, 2022 at 20:02
  • $\begingroup$ Sorry, I was confused a bit, I got your hint. It straightforward. $\endgroup$
    – Papa
    Commented Mar 5, 2022 at 20:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .