# Is an inﬁnite union of context-free languages always context-free?

Let $L_1$, $L_2$, $L_3$, $\dots$ be an inﬁnite sequence of context-free languages, each of which is deﬁned over a common alphabet $Σ$. Let $L$ be the inﬁnite 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?

• There are two mostly independent questions here. The first is very elementary, but the second is even easily answered with Wikipedia. I suggest you edit to focus on the first question. – Raphael Mar 10 '12 at 18:39
• @Raphael: I did it myself before your suggestion but then I thought it might make some parts of the answers useless. – Gigili Mar 10 '12 at 18:40
• @Raphael: That edit nullifies most of what I wrote! I don't think it is a good idea to be morphing questions like that, when there are answers already. – Aryabhata Mar 10 '12 at 19:24
• @Aryabhata: Is it possible to edit your answer please? I edited it to prevent the question from being easy as he said! I'll post a meta question about this. – Gigili Mar 10 '12 at 19:27
• @Gigili: I can, but I was talking in general terms. Imagine the case where someone does some research, and puts in some effort to write a detailed answer. Now you go and change the question which invalidates most of that answer. For this question it might not matter, in fact, I can probably just delete my answer, as we will have two answers saying the same thing and one of them would just be noise. – Aryabhata Mar 10 '12 at 19:44

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.

• Thank you for your answer. So the answer is "no"? Could you provide a counterexample? – Gigili Mar 10 '12 at 18:36
• @Gigili: the language $\{ a^n b^n c^n | n \geq 1 \}$ is the usual example of a language that is not context-free, and using my construction the union of $L_1 = \{ a b c \}, L_2 = \{ aa bb cc \}, L_3 = \{ aaa bbb ccc \}, \dots$ is exactly that language, but all the $L_i$ are finite and therefore context-free. – Alex ten Brink Mar 10 '12 at 18:38
• @Gigili You should be able to use any not context-free language as counter example using what Alex has written. – Raphael Mar 10 '12 at 18:40
• Another way to break down any language is according to the lengths of the words: $L = \bigcup_{n\in\mathbb{N}} \{w \in L \mid |w| \le n\}$. This shows that even an increasing union of finite languages is enough to describe any language. – Gilles 'SO- stop being evil' Mar 11 '12 at 20:21
• "In fact, the union of infinitely many languages can be just about anything" (emphasis added) Actually, it can be anything, period, no "just about". Your example shows that. Well, the null set/language may be an issue, but empty unions are fine. So, it can be the weirdest, vastly non-computable set, as far up any hierarchy as you'd like to go. It can be any set. – David Lewis May 11 '12 at 16:06