is $\{a^n b^m | n \neq m\} $regular or non regular?

Question

$\left\{a^nb^m\mid n \neq m \right\}\subset \{a, b\}$.

I have been asked to prove this is irregular but I think it is regular as I can write a regular expression a*b* for it. Am I wrong? If so how can I prove it is irregular with pumping lemma?

Answer 1

The regular expression $a^*b^*$ matches any string $a^nb^m$, so it gives you more than the language you want.

The simplest way to show that the language is not regular is to note that $$\{a^nb^n\mid n\in{\Bbb N}\} =\{a^nb^m\mid n,m\in{\Bbb N}\}-\{a^nb^m\mid n\ne m\}\ .$$ If your set were regular then the RHS would be regular, so the LHS would be regular. But the LHS is a standard example and I expect you have seen a proof that it is not regular.