0
$\begingroup$

Statement:

For any two languages $L_1$ and $L_2$ if $L_1 \cup L_2$ is regular, then $L_1$ and $L_2$ are regular.

Why is this statement false? Could somebody give me an example.

$\endgroup$
2
$\begingroup$

Pick $\Sigma = \{a,b\}$, $L_1 = \{ a^n b^n : n \in \mathbb{N}\}$ and $L_2 = \Sigma^* \setminus L_1$.

The union $L_1 \cup L_2$ is $\Sigma^*$ and hence is regular, but none of $L_1$ and $L_2$ is.

$\endgroup$
4
  • $\begingroup$ Why is $L_2$ not regular? $\endgroup$ – VimForLife Apr 12 '20 at 10:01
  • 1
    $\begingroup$ Because it is the complement of a non-regular language and regular languages are closed under complement. If $L_2$ was regular then so would be $\overline{L_2} = L_1$. $\endgroup$ – Steven Apr 12 '20 at 10:03
  • $\begingroup$ So if $L_2 = \Sigma^* \backslash L_1$ then $L_2 = \overline{L_1}$. $\endgroup$ – VimForLife Apr 12 '20 at 10:11
  • 1
    $\begingroup$ Yes. The definition of the complement $\overline{L}$ of a language $L$ is $\overline{L} = \Sigma^* \setminus L$. $\endgroup$ – Steven Apr 12 '20 at 10:14
0
$\begingroup$

Definitely not. Consider L to be non-regular, then L union its complement is the language of all words which is regular, but bot L and L complement are not.

$\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.