<p>Take an alphabet $A=\{0,1,2\}$, and $U=0^*+2A^*$. Then, $U^\omega$ is not deterministic Büchi recognizable.</p>

<p>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$.</p>

CC BY-SA 3.0
2014-08-19T17:14:02.993Z
2014-08-19T17:21:38.407Z
2014-08-19T17:21:38.407Z
Denis
<p>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. </p>

<automata-theory><regular-language><omega-language>
Example of a $U^\omega$ that is not Deterministic Büchi recognizable
Miheer
# Example of a $U^\omega$ that is not Deterministic Büchi recognizable

(Asked by: username_0 on 2014-08-19)

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.

**Tags:** automata-theory, regular-language, omega-language

---

## 1 answers

### Answer by username_1 on 2014-08-19. Score: 6 | Accepted answer

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$.


---

