proofpumping-lemma

proof L = {a^n b^m | n>=m} is irregular language


I am stuck in finding S for pumping lemma. is there any idea to proof that L = {a^n b^m | n>=m} is an irregular language?


Solution

  • The pumping lemma states this:

    If L is a regular language, then there exists a natural number p such that any string w of length at least p can be written as w = uvx where |uv| <= p, |v| > 0 and for all natural numbers n, u(v^n)x is also in the language.

    To prove a language is not regular using the pumping lemma, we need to design a string w such that the rest of the statement fails: that is, there are no valid assignments of u, v and x.

    Our language L requires the number of a's to be the same as the number of b's. The shortest string that satisfies the hypothesis that the string w has length at least p is a^(p/2) b^(p/2). We could guess this as our string. If we do, we have a few cases:

    1. v is entirely made of a's. But then, pumping is going to result in a different number of a's and b's, so the resulting string is not in the language; a condtradiction.
    2. v spans a's and b's. But then, pumping is going to cause a's and b's to be mixed up in the middle, whereas our language requires all the a's to come first. This is also a contradiction.
    3. v is entirely made of b's. But then, we have the same contradiction as in case #1.

    In all cases, this choice of w led to a contradiction. That means the guess worked.

    There was a simpler choice for w here: choose w = a^p b^p, then there is only one case. But our choice worked out fine. If our choice had not worked out, we could have learned from that choice what went wrong and chosen a different candidate.