zbMATH — the first resource for mathematics

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.

68Q45 Formal languages and automata
Full Text: DOI