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.

$\endgroup$
  • 2
    $\begingroup$ Try to think: what if, for example, $L_1=\Sigma^*$? What are then the conditions on $L_2$? $\endgroup$ – Shaull Nov 25 '15 at 12:59
  • 1
    $\begingroup$ So if $L_1$ = $\Sigma^*$ then $L_2$ must just accept nothing? $\endgroup$ – Aziz Nov 25 '15 at 13:00
  • 2
    $\begingroup$ Remember that $L_1$ and $L_2$ can have common elements. $\endgroup$ – Mike B. Nov 25 '15 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 Nov 25 '15 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. Nov 25 '15 at 13:21
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.

$\endgroup$

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.