# If two languages together cover all words and one is regular, is the other one as well?

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