# Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid?

Since $L_1$ is not regular, there does not exists a finite automata $M_1$ such that $L_1$ is the language of $M_1$. Pick $x\in L_1$. So $x \in L_2$ and suppose that $L_2$ is regular. Then there exists a finite automata $M_2$ such that $L_2$ is the language of $M_2$. Since $x \in L_2$ and $L_2$ is regular, there exists a state $s\in S$ such that from the initial state in $M_2$ there is a path $x$ to this final state $s$. Since this holds for all $x \in L_1$, we can construct a finite automata which language is $L_1$, so $L_1$ is regular, so we reached a contradiction, so $L_2$ is not regular.

Can this be done easier?

• I removed the second question as there should only be one question per thread. Please post a new question if this continues to be a problem. – Raphael Jun 28 '12 at 16:57

Since this holds for all $x\in L_1$, we can construct a finite automata which language is $L_1$.

And how would you do this? You have an infinite amount of paths in hands which you have to mold into a finite set of states and edges.

In fact, the statement does not hold.

Remember that $\Sigma^*$ is regular but there are non-regular languages.

• Thanks, but we have not treated MA yet. How can I do that without Minimal Algebra? So, there must be a counterexample. Let $L_1 = \{a^nb^n \mid n > 0\}$. What can I choose for $L_2$ to let the statement fail? Or am I thinking the wrong way? – Kevin Jun 28 '12 at 16:58
• @Kevin: What is "minimal algebra"? I won't give you more hints than I did; it is quite sufficient if you think about it (probably longer than two minutes). – Raphael Jun 28 '12 at 17:02
• Thanks. So, here is my counterexample: pick $L_1=\{a^n b^n | n > 0\}$ (not regular). $L_2=\{a^n b^m | n,m > 0\}$ (regular, can draw a finite automata for this). So $L_1 \subset L_2$ but $L_2$ regular. Is this right? – Kevin Jun 28 '12 at 19:55
• @Kevin: I think you can answer that yourself. – Raphael Jun 28 '12 at 20:58

I have a very simple counter example. Take $$L_2 = \Sigma^{*}$$ (where $\Sigma$ is the alphabet you are working over). Every language is a subset of $L_2$, in particular the non-regular languages are (strict) subsets of $L_2$, yet $L_2$ is regular.

A finite automaton accepting $L_2$ has only one state and this state is an accept state. For each $x \in \Sigma$ there is an edge going from the only state to itself.

• This also shows why it can't be true in general: The fact is that EVERY non-regular set is a subset of a regular set. – Sam Jones Jun 29 '12 at 12:09
• That's exactly what I wrote in my answer, if more elaborate. – Raphael Jun 29 '12 at 12:42