# 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. Commented Mar 10, 2012 at 18:39
• @Raphael: I did it myself before your suggestion but then I thought it might make some parts of the answers useless. Commented Mar 10, 2012 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. Commented Mar 10, 2012 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. Commented Mar 10, 2012 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. Commented Mar 10, 2012 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).
• @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. Commented Mar 10, 2012 at 18:38
• 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. Commented Mar 11, 2012 at 20:21