Is there a regular language $U$, for which $U^\omega$ is not a Deterministic Büchi recognizable language. I have been thinking over it for some time, but have been unable to come up with an example.
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Take an alphabet $A=\{0,1,2\}$, and $U=0^*+2A^*$. Then, $U^\omega$ is not deterministic Büchi recognizable.
To see this, imagine it is recognized by a deterministic Büchi automaton $\mathcal A$ with $n$ states. Then, look at the run of $\mathcal A$ on the word $w=2(0^{n+1}1)^\omega$. Any inside loop of $0$ must contain a Büchi state, because otherwise pumping yields a contradiction (we get a word of the form $2A^*0^\omega$ that is in $U^\omega$ but not accepted by $\mathcal A$). But then, it means that $w$ is accepted, and therefore $\mathcal A$ does not recognize exactly $U^\omega$.
