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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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.
-
-
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$– StevenApr 12, 2020 at 10:03
-
$\begingroup$ So if $L_2 = \Sigma^* \backslash L_1$ then $L_2 = \overline{L_1}$. $\endgroup$ Apr 12, 2020 at 10:11
-
1$\begingroup$ Yes. The definition of the complement $\overline{L}$ of a language $L$ is $\overline{L} = \Sigma^* \setminus L$. $\endgroup$– StevenApr 12, 2020 at 10:14
$\begingroup$
$\endgroup$
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.
