Pumping lemma in PDA and CFL

Question

I have an pumping lemma question I totally stuck on...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

is it CFL or not?

I quest it is not CFL because it is not enough to have one stack to remember al those conditions. You can remember that na (w) < nb (w) or na (w)< nc (w),nb (w) < nc (w) but not na (w) < nb (w) < nc (w). In addition I though that if the language is a^pb^2pc^3p and than if I pumped up |vy| for p times L is not CF however is it possible tu pump up for p times?

Or any idea for the solution?

is this a homework? it seems like a straightforward proof by contradiction — max taldykin, Apr 02 '12 at 20:41
btw, I just found two similar questions: http://stackoverflow.com/questions/4095509 and http://stackoverflow.com/questions/4149357 — max taldykin, Apr 02 '12 at 21:49

score 2 · Accepted Answer · answered Apr 02 '12 at 21:40

Note that Pumping lemma requires every string in L to stay in L after pumping. So, it is enough to get contradiction even for some specific form of strings in L.

a^pb^2pc^3p is a nice example but I suggest to try a shorter one: a^pb^p+1c^p+2.

The reasoning is almost the same as in the Wikipedia article: Pumping lemma:Usage. You will have the same five cases and it's quite straightforward to get contradiction in each one.

Pumping lemma in PDA and CFL

1 Answers1