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$
0
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.

$\endgroup$
2
  • $\begingroup$ Well, what about $x = a$, $y = a$, $z = b^pc^p$? There is more missed in revision 3 than picking a suitable $x$, and possibly something more important to understanding the scope of the pumping lemma for regular languages. $\endgroup$ – greybeard Feb 24 at 12:06
  • $\begingroup$ Greybeard it says “for every string in the language L”. There’s one string leading to a counter example, that’s enough. $\endgroup$ – gnasher729 yesterday
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).

$\endgroup$
0
$\begingroup$

The pumping Lemma is very abstract, yet very obvious if you check where it comes from.

If L is a regular language then there is a finite state machine with exactly P states. If you examine a string w of P or more symbols, then after processing P symbols you must have entered the same state twice. Say the first state entered twice is X, then w = axb where the string a moves from the initial state S to X, x moves from X back to X, and if w is in the language, then b moves from X to an accepting state. And the length of ax is at most P.

Processing ab would also move from S to X to an accepting state. axxb would move from S to X to X to X to an accepting state and so on. And that’s the pumping Lemma: If w is long enough then you must have entered a loop, and the string causing the loop can be repeated any number of times.

That’s why $ab^nc^n$ gives a counter example: Because the loop must contain a sequence of b’s or c’s; since one a is needed, it cannot be part of any loop. And that’s why $a^2b^nc^n$ doesn’t give a counter example: Because the second a forms a loop and therefore can be repeated any number of times, including zero times.

$\endgroup$
-1
$\begingroup$

$S = a^Pb^{PM}c^{PM}$. It can be divided in $S = xyz$ where $x = \epsilon, y = a^P, z = b^{PM}c^{PM}$ which satisfies the following conditions: $$ |xy| \le P $$ $$ xy^iz \in L $$ $$ |y| >= 1 $$ The middle condition is satisfied because the length of a is irrelevant to the length of b and c.

But, this doesn’t mean that a language is regular. The pumping lemma in simple words only says that: each regular language that can be represented with an automaton that has |finiteStates| = $x$, and the sequence it accepts is of length > $x$ then according to the pigeon-hole theorem, at least one state is looping.

The pumping lemma does not work both ways. Therefore a language that satisfies it is not necessarily regular. It only means that the ones with variable length that don't satisfy it are irregular.

New contributor
Someone is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • $\begingroup$ $P$ can be as big as you want, the lemma claims that there's pumping length $P > 1$ such that for every string $S$ of the language longer than $P$ the rest of the statements are valid. So we simply just choose $P > 1$. $\endgroup$ – Someone Feb 24 at 13:18
  • $\begingroup$ I'm sorry and thank you, it is |y| >= 1. My mistake $\endgroup$ – Someone Feb 24 at 18:27

Your Answer

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