Finite-state ω-languages

摘要

A class of ω-languages defined by structural properties instead of, as usually, by accepting devices is investigated. This class of finite-state co-languages, though being closely related to finite automata, differs essentially from the class of ω-languages accepted by finite automata. However, it turns out that up to the level Fσ ∪ Gδ of the Borel hierarchy both classes coincide, whereas they differ the first time in the levels Fσ and Gδ. The main tool in the proof of this statement the so-called normal form decomposition of finite-state ω-languages also provides in the case of ω-languages in Fδ ∪ Gδ a solution to the minimization problem of finite automata accepting ω-languages.