1
$\begingroup$

$\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to prove a language is non-regular. In reference to the Wikipedia article linked (see "Use of Lemma"), every string I have tried doesn't give a contradiction. For example, a string like $a^1b^pc^p$ (where $p$ is the pumping length) seems to nicely split into $x = \varepsilon$, $y = a^1$, $z = b^pc^p$. What am I missing here?

$\endgroup$
4
$\begingroup$

You've forgotten that $y$ can be pumped any number of times, including zero. The string $xy^0z = b^pc^p$ is not in the language.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Yes. Say $N$ is the constant of the pumping lemma, and consider $\sigma = a b^N c^N \in L$ and $\lvert \sigma \rvert = 2 N + 1 \ge N$. By the lemma, you can write $\sigma = \alpha \beta \gamma$, such that $\lvert \alpha \beta \rvert \le N$ with $\beta \ne \epsilon$ such that for all $k \ge 0$ it is $\alpha \beta^k \gamma \in L$. Now $\beta$ must be composed of only one symbol (in this case, as $\lvert \alpha \beta \rvert \le N$, it has to be only $a$ or some $b$s) as otherwise $\alpha \beta^k \gamma$ for $k > 1$ isn't of the right form ($a$s followed by $b$s followed by $c$s). Now $\alpha = \epsilon$, $\beta = a$ is impossible, because in that case you's have $\alpha \beta^0 \gamma = b^N c^N \notin L$. But $\beta$ just $b$s with $k \ne 1$ gives a string with number of $b$s and $c$s different, thus not in $L$. No division into $\alpha, \beta, \gamma$ works, the language fails the pumping lemma, it can't be regular.

Make sure you understand the lemma and it's use. Your proof is by contradiction, you need to prove the lemma doesn't apply. The lemma states that there is a constant $N > 0$ (i.e., you can't assume anything about $N$, just know it is positive) such that all strings in the regular language that are longer than $N$ (to get a contradiction, you can pick any convenient string that is long enough) can be divided into three parts with the given restrictions (i.e., you don't get to pick a convenient division, you have to prove none works), for that division all $k \ge 0$ pumpings belong to the language (given any division, you can pick some $k \ne 1$ that makes the pumped string not in the language).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy