Classes of Transfinite Sequences Accepted by Nondeterministic Finite Automata

Article type: Research Article

Authors: Wojciechowski, Jerzy

Affiliations: Institute of Mthematics, Warsaw University

Abstract: In this paper the notion of a nondeterministic finite automaton acting on arbitrary transfinite sequences is introduced. It is a generalization of the finite automaton on finite sequences and the finite automaton on ω-sequences. The basic properties of the behaviour of such automata are proved. The methods are shown how to construct automata accepting classes A ⋃ B, A ⋂ B, A ∘ B, A*, Aω, A# if we have automata accepting classes A and B. We prove that if a TF-automaton having k states accepts anything then it accepts an α-sequence for a certain, α∈{∑i=0mωi·ai:∑i=1mi·ai+a0⩽k}. Using the foregoing fact, we show that the family of classes definable by TF-automata is not closed with respect to the complement operation, that nondeterministic automata are not equivalent to the deterministic ones and that the emptiness problem for TP-automata is decidable. In the last section we show the construction of TP-automata defining sets {∗α} for α<ωω and having as few states as possible.

Keywords: finite automata, transfinite sequences, closure properties, emptiness problem, decidability

DOI: 10.3233/FI-1984-7203

Journal: Fundamenta Informaticae, vol. 7, no. 2, pp. 191-223, 1984