patternMajor
Is an infinite union of context-free languages always context-free?
Viewed 0 times
freelanguagesunioninfinitealwayscontext
Problem
Let $L_1$, $L_2$, $L_3$, $\dots$ be an infinite sequence of context-free languages, each of
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i.e., $L = L_1 \cup L_2 \cup L_3 \cup \dots $.
Is it always the case that $L$ is a context-free language?
which is defined over a common alphabet $Σ$. Let $L$ be the infinite union of $L_1$, $L_2$, $L_3$, $\dots $;
i.e., $L = L_1 \cup L_2 \cup L_3 \cup \dots $.
Is it always the case that $L$ is a context-free language?
Solution
The union of infinitely many context-free languages may not be context free. In fact, the union of infinitely many languages can be just about anything: let $L$ be a language, and define for every $l \in L$ the (finite) language $L_l = \{ l \}$. The union over all these languages is $L$. Finite languages are regular, but $L$ may not even be decidable (and thereby definitely not context-free).
The closure properties of context-free languages can be found on Wikipedia.
The closure properties of context-free languages can be found on Wikipedia.
Context
StackExchange Computer Science Q#206, answer score: 21
Revisions (0)
No revisions yet.