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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityStatement:
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.
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.
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.