A nondeterministic automaton is finitely ambiguous if for each input there is at most finitely many accepting runs. We prove that the complement of the ω-language accepted by a finitely ambiguous Buechi automaton with n states is accepted by an unambiguous Buechi automaton with 2×5~n states.
展开▼
