pumping-lemma

Is the language L ={a^n b^k c^m | k>=0, n>m} regular?

I have to explain using the pummping-lemma that the language:

L ={a^n b^k c^m | k>=0, n>m}

is not regular.

Can someone please explain how it is done on this particular language?

Solution

  • EDIT: I made 2 mistakes here, first the pumping must be related to the word you use ( or at least it seems so after watching a lot of examples ), Secondly, its the other way around if you find any good match, then you cant use it as a wrong example. Provided my answer was wrong i ll edit with how it can really be proved.

    The pummping lemma is about proving that is not a regular language by using contradiction, you first have to assume a string you provide that must be valid for L is regular, then you have to divide this string into 3 parts following some rules:

    1. |y| > 0
    2. |xy| <= P (P represents the minimun length of the word)
    3. xy^nz with n>=0 is included in the language (L)

    So lets take for example P is 1:

    For using this one i ll not use any b's provided the language allows it. What this means is i ll have my language expressed this way L = { a^P+1 c^P } which is included in L and is valid so lets say aac (this one is in L)

    With this in mind you can prove is not regular using 2 of the 3 statements

    |xy| is greater than P because P is 1 and xy is 2

    xy^nz if we use n = 0, then the result would be ac which is not included in the language.