Theory of ω-languagesI: Characterizations of ω-context-free languages

摘要

An ω-language is a set consisting of ω-length strings over some alphabet; an ω-automaton is a device capable of recognizing ω-length input tapes. This paper introduces the basic notions concerning generation of ω-languages by means of ω-grammars and their recognition by ω-automata with various recognition modes. Attention is focused on ω-CFL's, the ω-languages generated by ω-context-free grammars. Two main characterizations of the family of ω-CFL's are obtained. (a) An ω-language is an ω-CFL if and only if it can be represented as Ui=1/nUiVi/ω, where for each i=1,…, n, Ui and Vi are context-free languages. (b) ω-CFL's are precisely the ω-languages recognized by ω-pushdown automata of three distinct types. A few other characterizations and normal forms for the ω-CFL's are obtained and several decidability results are established.