It is known that union of two context-free languages is also context-free.
But how about union of context-free and non-context-free languages?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Not in general. Consider a language $L$ over some alphabet $\Sigma$ such that neither $L$ nor its complement $\overline{L}$ is a decidable language. It is obvious that neither of these languages can be context-free. But $L \cup \overline{L} = \Sigma^*$, which is a context-free language.
And consider $\emptyset$, which is trivially a context-free language. Clearly $L \cup \emptyset = L$ is not a context-free language.
