How to prove non-regularity of a language from the non-regularity of another language?

Question

How can I prove that $L_1=\{a^nb^m\mid n\ne m\}$ is not regular based on the fact that the language $L_2=\{a^nb^n\mid n\in\Bbb N\}$ is not regular?

Thank you

Answer 1

HINT: If $L$ is a regular language over the alphabet $\Sigma$, then $\Sigma^*\setminus L$, the complementary language consisting of words in $\Sigma^*$ that are not in $L$, is also regular. (This is quite easily proved using DFAs.)

Answer 2

Here is some facts:

1)A language L is regular if and only if L-complement is regular.

2)Intersection of two regular languages is regular.

In your question, L1-complement is L2 union all string containing the sub-string 'ba'. L2= L1-complement intersect with 'a* b*'. We know that 'a* b*' is regular(Because we gave an explicit regular expression for it) . Therefore, L1 is regular implies L2 is regular by the above two facts contradiction. Thus, L1 must not have been regular.