×

Ensembles reconnaissables de mots biinfinis. (French) Zbl 0619.68067

A biinfinite word on the alphabet A is a function w from the set of integers Z to A. Let \(U=(Q,F,I,T)\) be a finite automaton where Q is the set of states, F is the transition function, I is the set of initial states and T is the set of terminal states. We say that U accepts the biinfinite word \(w=...w_{-1}w_ 0w_ 1..\). iff for the sequence of states induced by F, \(...q_{-1}q_ 0q_ 1...\), there are an infinity of integers \(n\leq 0\) such that \(q_ n\in I\) and an infinity of integers \(n\geq 0\) such that \(q_ n\in T\). We denote by \(Rec(A^ Z)\) the family of sets accepted by finite automata and by \(Det(A^ Z)\) the family of sets accepted by deterministic finite automata. The main result of the paper establishes that the family \(Rec(A^ Z)\) is the Boolean closure of the family \(Det(A^ Z)\). This result is an extension of the McNaughton Theorem from the case of infinite words to biinfinite words.
Reviewer: D.Lucanu

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI