0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael Jun 28 '12 at 16:57
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kevin Jun 28 '12 at 16:58
  • $\begingroup$ @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). $\endgroup$ – Raphael Jun 28 '12 at 17:02
  • 1
    $\begingroup$ 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? $\endgroup$ – Kevin Jun 28 '12 at 19:55
  • 1
    $\begingroup$ @Kevin: I think you can answer that yourself. $\endgroup$ – Raphael Jun 28 '12 at 20:58
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sam Jones Jun 29 '12 at 12:09
  • $\begingroup$ That's exactly what I wrote in my answer, if more elaborate. $\endgroup$ – Raphael Jun 29 '12 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.