Any one counter language that is not nonterminal bounded must contain an infinite regular set; every generator of the family of one counter languages must contain an infinite regular set. Any language that is in the substitution closure of the linear and one counter languages but is not derivation bounded must contain an infinite regular set.
The Chomsky-Schiitzenberger Theorem established the Dyck set on two letters as a generator of the family of context-free languages [3]. Since then several facts have been learned about context-free generators, primarily that they have many of the nice features of the Dyck sets [8,11]. It was shown that the family of contextfree languages which are not generators is a full AFL closed under substitution [8]. The exact identity of this full AFL remains an open question. One simple guess was the following (subsequently disproved [15]).
Conjecture 1. A context-free language is either a generator of the family of context-free languages or it belongs to the substitution closure of the linear and one counter languages.
Let ~ be the substitution closure of the linear context-free languages and 5t the substitution closure of the linear and one counter languages. Although one can use AFL theory to obtain a very short proof that there are context-free languages not in .~, it is generally a tedious matter to give a complete proof that a particular language is not in ~ (cf. [13,14] for example), and even harder to show that a language is not in Y. In this note we offer a simple condition under which a language not in cannot be in 5 P. Namely, a language that does not contain an infinite regular set cannot be in J --~. This follows easily from our main result: a one counter language that does not contain an infinite regular set (IRS) must be nonterminal bounded.
This condition (no subset is both infinite and regular) which we may call the IRS condition, turns up in other connections when studying the structure of the family of context-free languages. One example is the result in [11] that a context-free language which satisfies the IRS condition is uniformly erasable if and only if it