As in, given a regular language $V$, does there exist a deterministic Büchi automaton $\mathcal{A}$, or equivalently a regular language $W$ such that $\mathcal{L}(\mathcal{A})=\vec{W}=V^\omega$?

For clarity, if $L$ is a finite-word language, then $L^\omega$ and $\vec{L}$ are resp. the $\omega$-closure and the limit of $L$; see here.

Edit: My guess is that $V^\omega=\vec{V^\ast}$, but I'm unable to (dis)prove it. see comments.

  • $\begingroup$ Regarding your conjecture: it probably is not simple as that. In a paper by Choueka, Theories of automata on $\omega$-tapes, we find the following Lemma 5.2: For every regular $V \subseteq X^*$ one can effectively find some regular $\widetilde V \subseteq X^*$ such that $V^\omega = V^* ( \lim \widetilde V)$. $\endgroup$ Commented Apr 28, 2022 at 16:34
  • 1
    $\begingroup$ Quoting from the same paper, just above the lemma: Certainly one cannot say, in general, that $V^\omega = \lim V$ or $V^\omega = \lim V^*$: the set $V = \{1\}\{0\}^*$ is a counterexample to both assertions, since $10^\omega$ is not in $V^\omega$ although it is in $\lim V$ and in $\lim V^*$. $\endgroup$ Commented Apr 28, 2022 at 16:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.