Every non-terminal in the corresponding context -free grammar should be non-repeating in the derivation (should be terminating in terminals(alphabets) and transition diagram should not have a cycle).

Dear R.C. Mittal,

  Could you be a bit more explicit about necessity and sufficiency?  I am very interested in your answer.

  Best Wishes,

  Collin

@Collin: We are assuming for each context free language Ci, set of non-terminals Ni is finite. Now the language generated will be finite if every non-terminal is eventually terminated into alphabets which will be finite. If non-terminals get repeated then it will keep on calling it self and you get infinite many alphabets. Basically transition diagram of the grammar should not a cycle so that repetition does not take place.  

I do not immediately know the answer, but I think you may find leads in Damian Niwinski's 1984 article about fixed points and context-free languages: http://www.sciencedirect.com/science/article/pii/S0019995884800492

Thanks to all for your answers.  I am going to go do some reading and get back with my take on these ideas.

@R.C. Mittal:  Perhaps I do not understand your answer, since one can certainly build NON-context free languages even as unions of finite (regular) languages over a fixed alphabet.

In my conditions, I also have fixed the same (finite) alphabet for all the languages.

OK, thanks all!

Are there well-known similar results for regular languages? Or are the questions for regular and context-free languages of independent interest and difficulty?

Dear @Claude Tardif,

Thanks for your question.  Sasha Rubin pointed out to me a few months back that the question is just as valid for regular languages.  And runs into the same trivial argument:  one needs a good condition, as it is easy to build an ascending union of regular languages that will not be a nice language of any sort.

 However, for regular languages, I think it is easier to resolve what happens if the union is to remain regular.  One should run into a Noetherian condition very quickly.  Anyway, this conversation has inspired me to try to answer this question for regular languages, and I should be done (successfully, or stumped) in the next day or two.  I will report back then.  

Thanks again for the question.

For the instance it looks bad.... Consider an alphabet consisting of one terminal a. Consider a language L \subset a* that is not context-sensitive, or even not recursively enumerable, or even not arithmetic. L is so bad if you please. Now let L = {w_n} be some enumeration of L. Let L_n be the finite set {w_1, ... , w_n}. Being finite, the languages L_n can be produced by REGULAR grammars, and we can arrange that the non-terminal alphabets and the sets of production rules form ascending chains of sets. At the first sight it looks like you can produce things which are so bad as you please as unions of regular languages. Maybe the problem becomes more interesting if we try to  look only at the following situations: the regular or context-free languages L_n are all infinite, and the non-terminal alphabets live in a chain that become stationary (or, to simplify, is always constant). Now, the sets of production rules cannot be strictly increasing - or it is, but finally the infinite set of productions will be equivalent with a finite one. I am affraid that only trivial cases will remain, but I do not know the answer.

Right Mihai,  this is exactly the point.  You can make any countable language (say, any language on a finite alphabet) as an infinite union of finite (and therefore regular) languages.

So the point is that under what conditions will the ascending union not break it's class.

From the basic definition of set, there is no order in the elements of the set, if way say order just it is an index, from the definition and we know that two CFL's are union, then the infinite ascending union of context free languages result in a context free language

Sorry Karibasappa,

  In fact, it is easy for an infinite ascending union to not be a CFL even though all the finite unions are CFL's.

As an example, one can build ANY language on a fixed alphabet as a union of finite languages.  Finite languages are themselves context free.

A context-freeness preserving dependency between the C_i might work. For example if there is a finite set of transducers such that always C_{i+1} = T(C_i) for one of the transducers. Without bound on the number of transducers, the example of union of finite sets would work. But for a finite number, maybe all the possibilities in which they can combine could be foreseen in a "context-free manner." 

@peter:

Yes, it is exactly a condition like this which seems to work for the regular languages too, although nailing it down seems a bit tricky.

Good work!

Well, I guess that if finite transducers work for CF they will do so for REG, too. If you want some transformation that does not work for REG, you could look at context-free string-rewriting systems. The result of the transformation is the language of all the words that can be reached via SRS-rules from words of the original language. Here the proof would be trivial, since the union of the SRS would reach the same result in just one step. Maybe if you do not take all the words but only those reachable in a fixed number of steps. The limit is the same and CF, but here the chain can be infinite and truly ascending. Of course, it is a bit artificial. But every step preserves regularity, while the result can be any context-free language.  

Right,

I am not too interested in what works for CF but not for REG, I am just continuing an earlier thread of this topic which points out that the question is also valid for REG, not just CF.

Finite transducers will preserve CF languages, but the point is to find a condition on the languages C_i so that you will already know that their union will still be CF.

In your last post you point out that your proffered construction is trivial; assuming the result is CF, then you can build an ascending union of regular that works.  I agree, and give more details below as an example.  What I am hoping for is a general condition on the C_i, which will guarantee that the union will be CF, without just taking an assumption obviously equivalent to ``their union is CF.''

Here is you point in more details, for interested readers:

  Take an infinite CF language L which is not regular, over fixed finite alphabet A.  Set C_i to be all the words in L of length less than or equal to i.  Each of the C_i is now a finite regular language.  Infinitely often, C_i is smaller in cardinality than C_{i+1}, so that C_{i+1} is not an image of C_i under any transducer.

Alright. So I would refrase your problem slightly.

If the only condition on the C_i is the inclusion, I do not think that there can be a general condition guaranteeing anything about their union. It must be a condition on the way in which C_{i+1} depends on / is produced from C_i. If you look only at C_i, then there is nothing to work with, informally speaking.

The summary of my point is not completely correct. We can start with an arbitrary subset of the limit language that contains all the minima under the string-rewriting relation. All the C_i can be infinite, C_1 can already contain words of any length.  

@Peter Leupold,

  I did understand your full point, I just gave my example with finite C_i to highlight that the limit could be from regular languages (to anything) and also so that the argument for the failure of the existence of onto transducers (as you went from C_i to C_{i+1} would be more obvious.

OK, good discussion, all around, thank you.

@Stefan and @Peter T Breuer,

  Sorry Stefan, Peter's comment is correct.  Mogensen's comment refers to finite unions.  As you can see from some of the early comments on this thread, one can build ANY infinite language L (So, L is a subset of X^* for X a finite alphabet), not just CF languages, as an infinite ascending union of finite (so, CF) languages.

@Stefan,

Thanks, and indeed, this is the sort of discussion I am trying to have.  I fully agree with your last comment.  From a PDA perspective, there is a minimal PDA that works for each C_i, and eventually, there will be a universal minimal PDA that will accept each of the Ci languages, and for which each word accepted by this PDA will appear as an accepted word in the PDA's of one (and all later) of the Ci languages.

This special PDA is basically a ``quotient'' of the graph structure of later PDAs, but this quotient will sometimes add infinitely many words (that indeed appear in the later Ci).  This correlates to a single terminal symbol now terminating the construction of infinitely many words in the grammar (instead of always needing to add more terminals).

So, the issue is whether one can ascertain this happens (a finite quotient PDA, or a finiteness condition on necessary terminals, if you will) by looking at the properties of the Ci ``along the way,'' or perhaps more importantly, make a cogent argument that this does not happen (ie, argue, in your context, that eventually some new terminals will be required); so we can say a result will not be a CF language (better than the current versions of Pumping Lemmas, etc.).

OK, good points.  Thanks again!

                          -Collin

Hi!

If you start with a CF language, e.g., the palindromes over the binary alphabet,

and adding words of another CF language, e.g., a^nb^n one-by-one starting, from the shortest ones, not excluding any, 

the union at every time is a CF, since finite union (e.g. union of a CF and a finite language in this case) is CF. Also, in the limit the union of two infinite CF languages is obtained that is also a CF language.

(Of course to find not only examples, but if and only if conditions would be much harderm if possible at all.)

@Benedek,

  Thanks!  Indeed it is the case that the union of two infinite CF Languages is a CF Language, and your construction DOES build this resulting language as an infinite union of nested CF languages, so that is in keeping with the question as posted.

  However, at first blush, this produces a generalisation of the form ``the union of infinitely many nested CF Languages is a CF Language if the resulting language can already be written as a union of two CF Languages."  While surely true, we will need to do some work on this to make it more directly usable.

Still, it may be that this viewpoint can lead to information about excess terminals or branching as in earlier suggestions above, and your contribution is appreciated.