Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

135 Views Asked by At

In the Book Infinite Words (homepage) it is proofed that:

If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent:

(1) $X$ is closed

(2) $X$ is recognized by a deterministic Büchi automaton in which each state is final.

But I am not sure if this is correct? First in the proof (given below) of "(4) implies (2)" why is $Pref(X)$ a regular language, so that an automaton could be given. Furthermore, the following example of $\{ u \}$ as a closed set contradicts the Proposition, because $\{ u \}$ is closed, but might not be recognizable by an Büchi automaton (and so also not by a determinstic Büchi automaton).

enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

Well, in Proposition 3.7, neither $X$ nor $Pref(X)$ are supposed to be regular. Automata can be infinite in this proposition. The regular case is treated later, in Proposition 3.9.