## Fixed-point characterization of context-free $$\infty$$-languages.(English)Zbl 0591.68075

Summary: Several concepts of context-freeness of sets of finite/infinite words are characterized by means of greatest solutions of systems of equations of the form $$x_ i=G_ i$$, $$i=1,...,n$$, where $$G_ i$$ is a (not necessarily finite) union of monomials. Consideration of the systems with the components $$G_ i$$ context-free, regular or finite leads to characterizations of the following classes of $$\infty$$-languages: the $$\omega$$-Kleene closure of the family of context-free languages, $$\infty$$-algebraic languages infinitely generated by context-free grammars in the sense of M. Nivat [RAIRO, Inf. Théor. 11, 311-327 (1977; Zbl 0371.68025)] and Cantor-like topological closures of context- free languages, respectively.

### MSC:

 68Q45 Formal languages and automata

Zbl 0371.68025
Full Text: