Theory of ω-languages. II: A study of various models of ω-type generation and recognition

摘要

ω-languages are sets consisting of ω-length strings; ω-automata are recognition devicesfor ω-languages. In a previous paper the basic notions of ω-grammars, ω-context-free languages (ω-CFL's), and ω-pushdown automata (ω-PDA's) were first defined and studied. In this paper various modes of ω-type generation are introduced and the effect of certain restrictions on the derivations in ω-grammars is investigated. Several distinct models of recognition in ω-PDA's are considered, giving rise to a hierarchy of subfamilies of the ω-CFL's. The relations among these subfamilies are established and characterizations for each family are derived. Non-leftmost derivations in ω-CFG's are studied and it is shown that leftmost generation in ω-CFG's is strictly more powerful than non-leftmost generation.