Search code examples
pumping-lemmacontext-free-language

Pumping Lemma for CFL a^n b^m c^o for n<m<o


Let be: L={an bm co | n < m < o, n natural}
Using Pumping Lemma I have choosen: z = uvwxy = an bn+1 cn+2
|uv|<=n and |v|>0
=> uv2wx2y
If vwx is of a's and / or b's it is okay and we would have more a's and/or b's than c's - but if vwx contains only c's it would be element of L.
As far as I understood all new words have to be not element of L to show that it is not a CFL. How would I do this?


Solution

  • If we have a mix of a's & b's use uv2wx2y
    If we have a mix of b's & c's use uv0wx0y

    Now all words that are created by pumping z are not element of L.