11
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael♦ Mar 10 '12 at 18:39
  • $\begingroup$ @Raphael: I did it myself before your suggestion but then I thought it might make some parts of the answers useless. $\endgroup$ – Gigili Mar 10 '12 at 18:40
  • $\begingroup$ @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. $\endgroup$ – Aryabhata Mar 10 '12 at 19:24
  • $\begingroup$ @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. $\endgroup$ – Gigili Mar 10 '12 at 19:27
  • $\begingroup$ @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. $\endgroup$ – Aryabhata Mar 10 '12 at 19:44
21
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. So the answer is "no"? Could you provide a counterexample? $\endgroup$ – Gigili Mar 10 '12 at 18:36
  • 4
    $\begingroup$ @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. $\endgroup$ – Alex ten Brink Mar 10 '12 at 18:38
  • 5
    $\begingroup$ @Gigili You should be able to use any not context-free language as counter example using what Alex has written. $\endgroup$ – Raphael♦ Mar 10 '12 at 18:40
  • 3
    $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Mar 11 '12 at 20:21
  • 4
    $\begingroup$ "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. $\endgroup$ – David Lewis May 11 '12 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.