4
$\begingroup$

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.

$\endgroup$
2
  • $\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

1 Answer 1

0
$\begingroup$

I assumed that $\vec{R}$ is the language of infinite words $w$ that have infinitely many prefixes in $R$, a.k.a $lim(R)$.

Consider a deterministic Büchi automaton $\mathcal{A} = (\Sigma, Q, q_0, \delta, \alpha)$, and let $\mathcal{A}_f$ denote $\mathcal{A}$ when viewed as an automaton over finite words. As both automata are deterministic, it is not hard to show that $L(\mathcal{A}) = lim(L(\mathcal{A}_f))$. Indeed, if we consider two runs of $r_x$ and $r_y$ where $x$ is a prefix of $y$, then the run $r_y$ extends the run $r_x$. In particular, if an infinite word $w$ has infinitely many prefixes $x_1 < x_2 < x_3 < \ldots$ (by $x_i < x_j$, we mean that $x_i$ is a proper prefix of $x_j$) in $L(\mathcal{A}_f)$, then their corresponding runs induce a unique accepting run of $\mathcal{A}$ on $w$.

It is also not hard to prove the converse similarly. Meaning, for every DFA $\mathcal{A}$, let $\mathcal{A}_B$ denote $\mathcal{A}$ when viewed as a Büchi automaton, then it holds that $L(\mathcal{A}_B) = lim(L(\mathcal{A}))$. Thus, we can conclude with the following:

Claim[reference]: A language $L$ over infinite words is recognizable by a deterministic Büchi automaton iff there is a regular language $R$ such that $L(\mathcal{A}) = lim(R)$.

Now consider a regular language $R$. Regarding whether the language $R^\omega$ is always deterministic-Büchi-recognizable, the answer is negative and a counter-example was recently shown here. So the answer to your question is negative, although the limit of every regular language is deterministic-Büchi-recognizable.

Edit: The specific counter-example is given by the regular expression $$R = $ \cup (0 \cdot (0\cup 1 \cup $)^*\cdot1)$$
Note that the only way to have only finitely many 1’s in a word in $R^\omega$ is to have an infinite tail of $\\\$$’s. Therefore, it follows that for every word $w\in R^\omega$, if $w$ contains infinitely many 1’s, then $w$ contains infinitely many 0’s. The latter implies that the word $$ w=011\text{$\\\$$}1\text{$\\\$$}\text{$\\\$$}1\text{$\\\$$}\text{$\\\$$}\text{$\\\$$}1\text{$\\\$$}\text{$\\\$$}\text{$\\\$$}\text{$\\\$$}\cdots = 0\cdot \prod_{i=0}^\infty 1\text{$\\\$$}^i$$

is not in $R^\omega$. It is not hard to see however that $w \in R^\# = \{w\in \Sigma^\omega: \text{ for all $i\geq 1$ there exists a prefix of $w$ in $R^i$}\}$, and this implies that $R^\omega$ is not deterministic-Büchi-recognizable as the authors prove the following claim:

Claim: Consider a regular language $R$. Then, $R^\omega$ is deterministic-Büchi-recognizable iff $R^\omega = R^\#$.

$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.