If language L is not regular, and L ⊂ M. Do we know if M is regular or not?

Question

I have been given some questions to do regarding regular/irregular languages. And have the following questions

True/False

(i) If L is not regular and L ⊂ M, then M is not regular.

(ii) If L ⊂ M and M is not regular, then L is not regular.

(iii) If L is not regular, then its complement {a, b}* \ L is not regular.

(iv) If L is regular, then L ∪ M is regular for any language M.

What rules do I need to know to figure these questions out? Can someone point me in the right direction. I'm not asking you to do these for me, although I may ask for you to check answers.

Answer 1

In order to tackle these questions, it's useful to know what is and what isn't a regular language :-). Wikipedia is helpful. http://en.wikipedia.org/wiki/Regular_language

Regarding question (ii), for example, we can take $M = \left\{a^nb^n \mid n \in \mathbb N_0\right\}$ and $L = \left\{ab\right\} \subseteq M.$ Since $M$ is not regular, but $L$ is, (ii) is false.

(i) is false, too. Take $M = \left\{a^ib^j\mid i,j \in \mathbb N_0\right\}$ and $L = \left\{a^nb^n \mid n \in \mathbb N_0\right\} \subseteq M$. $M$ is regular since it's recognized by the regular expression $a^*b^*$, but $L$ is not regular (according to Wikipedia :-). So (i) is false.

(iv) is false, too. A counterexample are $L$ and $M$ from my answer to (ii). $L$ is regular, but $L\cup M = M$ is not.

Answer 2

(i) is clearly false. Take $L$ any non-regular language over the alphabet $A$ and $M=A^*$ (which is regular).

(ii) is clearly false, too. Take $L=\emptyset$ (which is regular) and M any non-regular language.

(iii) is true. The complement of a regular language is always a regular language. Therefore, the complement of a non-regular language must be non-regular. Indeed, suppose that $L$ is a non-regular language and assume by contradiction that $L^c$, its complement, is regular. Then $(L^c)^c)$ is regular. But $(L^c)^c)=L$, and we assumed that $L$ is regular. So we have a contradiction and the claim is therefore true.

(iv) is clearly false. Again, take $L=\emptyset$, so that $L\cup M=M$ for any $M$. If the statement was true, then every language would be regular.