Given the following question:

Prove that the following language is not a regular language:

A language L in alphabet $\Sigma = \{a, b\}$ where every word $w$ have more $a$ than $b$.

How would you prove that it's not a regular language?

I need help and any hint is welcome.

Thanks in advance.

  • 5
    $\begingroup$ Use the pumping lemma for regular languages. $\endgroup$ – Jost Nov 7 '14 at 14:10
  • 1
    $\begingroup$ Or the Myhill-Nerode equivalence theorem (en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem). I find this to be much more convenient than the pumping lemma in most cases. $\endgroup$ – PhoemueX Nov 7 '14 at 14:53
  • $\begingroup$ The Myhill-Nerode theorem is definitely the way to go here. $\endgroup$ – MJD Nov 7 '14 at 16:00

One way is to use the pumping lemma for regular languages; the linked article has an example of how to use it. If you try that approach with the word $w=b^pa^{p+1}$, where $p$ is the pumping length, you’ll get the desired contradiction very easily. I find this the easiest approach, but you can also use the Myhill-Nerode theorem. If you use it, you might ask yourself whether any of the strings $a^k$ for $k\in\Bbb N$ have distinguishing extensions.

  • 1
    $\begingroup$ It would be interesting to know the basis for the downvote of a correct answer; in my book that’s vandalism. $\endgroup$ – Brian M. Scott Nov 7 '14 at 20:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.