How to prove that a language `L` is not a regular language?

Question

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.

Answer 1

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.