Affiliations: College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, 210016 Nanjing, Jiangsu, China | LAAS-CNRS, INSA, Université de Toulouse, 135 Avenue de Rangueil, 31077 Toulouse, France. zhechen@nuaa.edu.cn; zchen@insa-toulouse.fr
Note: [] Address for correspondence: College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, 29 Yudao Street, 210016 Nanjing, Jiangsu, China
Abstract: An ω-grammar is a formal grammar used to generate ω-words (i.e. infinite length words), while an ω-automaton is an automaton used to recognize ω-words. This paper gives clean and uniform definitions for ω-grammars and ω-automata, provides a systematic study of the generative power of ω-grammars with respect to ω-automata, and presents a complete set of results for various types of ω-grammars and acceptance modes. We use the tuple (σ, ρ, π) to denote various acceptance modes, where σ denotes that some designated elements should appear at least once or infinitely often, ρ denotes some binary relation between two sets, and π denotes normal or leftmost derivations. Technically, we propose (σ, ρ, π)-accepting ω-grammars, and systematically study their relative generative power with respect to (σ, ρ)-accepting ω-automata. We show how to construct some special forms of ω-grammars, such as ϵ-production-free ω-grammars. We study the equivalence or inclusion relations between ω-grammars and ω-automata by establishing the translation techniques. In particular, we show that, for some acceptance modes, the generative power of ω-CFG is strictly weaker than ω-PDA, and the generative power of ω-CSG is equal to ω-TM (rather than linear-bounded ω-automata-like devices). Furthermore, we raise some remaining open problems for two of the acceptance modes.
Keywords: ω-automaton, ω-grammar, ω-language, generative power
