Families of Languages," abbreviated full AFL's, were introduced by S. Ginsburg and S. Greibach in [I 1]. It is well known that the family of contextfree languages is a full AFL . It is also a rational cone (according to Eilenberg's terminology) . Let Dn* (respectively, D~*) be the Dyck language (respectively, semi-Dyck language) on 2n letters, ai, 5i, i = 1,..., n, i.e., the class of 1 in the congruence generated by (7i5 i = 5i(7 i ~ 1 (respectively, aiSi = 1) . The Chomsky-Schtitzenberger theorem implies that, for any n >~ 2, D~* (respectively, D~*) is a full generator of the AFL as well as of the rational cone of the context-free languages. It seems, then, natural to look at the rational cones and the AFL's generated by the Dyck languages DI* and the semi-Dyck language DI* on two letters.
We proved elsewhere [2] that the rational cone W generated by D~* can be characterized by the structure of the pushdown automata recognizing the languages in cg.
The main restriction we impose on them is that they should use a single pushdown symbol. Since we can consider the pushdown store as a counter, we call such an automaton a "one-counter automaton" and we call one-counter languages the elements of ~7. It is rather important to notice that this family W is not the family ~ studied by Greibach in . However, o~ and c# are closely related: o~" is the full AFL generated by Di* . Consequently, from a result of restated in [3], o~-is the closer of under union, product, and star operation.
In this paper, we prove two pumping lemmas (Theorems 3 and 4) which yield corollaries such as:
Neither DI* , nor D'a* can be mapped one on the other by any rational transduction (= mapping performed by an a-transducer [1 I]).
The full AFL's they generate are different and strictly included in the AFL of contextfree languages.
In the first part of this paper, we recall some notations, terminology, and properties we use about Dyck languages and rational transductions. In the second, after further definitions, we state our two theorems and prove several corollaries. The proof of these two theorems is given in a third part.
The main results of this paper have already been given, without any proof, in .