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

Niwiński, Damian

Inf. Control 61, 247-276 (1984).

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

Keywords:

finite/infinite words; Kleene closure; context-free languages; algebraic languages; Cantor-like topological closures

Citations:

Zbl 0371.68025