1
$\begingroup$

If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ necessarily regular?

I think that the answer is yes, but I'm not sure on my proof.

The reason that I think that $L_2$ is regular is because surely $L_2$ just accepts all the words in the language that $L_1$ doesn't? So, to me, that suggests that $L_2$ must be regular as well, I just don't know where to begin on a formal proof.

Any guidance would be appreciated.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ Try to think: what if, for example, $L_1=\Sigma^*$? What are then the conditions on $L_2$? $\endgroup$
    – Shaull
    Commented Nov 25, 2015 at 12:59
  • 1
    $\begingroup$ So if $L_1$ = $\Sigma^*$ then $L_2$ must just accept nothing? $\endgroup$
    – Aziz
    Commented Nov 25, 2015 at 13:00
  • 2
    $\begingroup$ Remember that $L_1$ and $L_2$ can have common elements. $\endgroup$
    – Mike B.
    Commented Nov 25, 2015 at 13:04
  • 1
    $\begingroup$ Of course... So if $L_1$ = $\Sigma^*$ then $L_2$ $\subseteq$ $\Sigma^*$ still... But I don't see that helps me? Do I have to use $L_2$ to produce a non-regular language? $\endgroup$
    – Aziz
    Commented Nov 25, 2015 at 13:08
  • 1
    $\begingroup$ Well, what happens if you choose a non-regular language for $L_2$? Can you find one s.t. $L_1 \cup L_2 = \Sigma^*$ when $L_1 = \Sigma^*$? $\endgroup$
    – Mike B.
    Commented Nov 25, 2015 at 13:21

1 Answer 1

Reset to default
4
$\begingroup$

In fact, the answer is no.

If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ is not necessarily regular.

We can prove this through counter-example.

If we let $L_1$ = $\Sigma^*$, then we can choose any non-regular language in $\Sigma$ for $L_2$.

If we take $\Sigma$ = {a,b} and then let $L_2$ = $a^n$$b^n$ (A non-regular language) then $L_1$$\cup$ $L_2$ = $\Sigma^*$ and $L_2$ is non-regular as required.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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