Given a regular language $U$, when does there exist $V$ such that $U^\omega$ = $\lim V$?

Question

What I know is that $W = \lim V$ for some $V$ if and only if $W$ is the language of some deterministic buchi automata, namely that of $V$.

So, to attack this problem I tried to come up with some language of the form $U^\omega$ which cannot be determinized. But I keep failing trying to come up with something like this.

Is it true in general that given regular $U$, there is some regular $V$ such that $U^\omega$ = $\lim V$?

Answer 1

Consider the language $$U = U_1 \mid U_2 = a\Sigma^* \mid (\Sigma \setminus \{c\})^* b$$ for the alphabet $\Sigma = \{a,b,c,d\}$.

Let $\mathcal{A}$ be a deterministic Büchi automaton for the language $U^\omega$ with $n$ states. For every $n \in \mathbb{N}$, the word $w_1 = a(b^n c)^\omega$ should not be accepted, but the word $w_2 = a(b^n c)^m b^\omega$ should be accepted for every $m \in \mathbb{N}$.

The word $w_1$ should not be accepted because $U_1$ can only be used once (as there is only one $a$ in $w_1$), so in order for $w_1$ to be be accepted by $U^\omega$, a subword match with $U_2$ has to occur infinitely often -- but $U_2$ cannot accept subwords with a $c$.

The word $w_2$ should be accepted because $U_1$ accepts $a(b^n c)^*$, and $(U_2)^\omega$ accepts $b^\omega$.

Now by a pumping argument, we can see that from a prefix trace for a, when reading $b^n$, an accepting state in the Buchi automaton should be visited at least once, as otherwise we have a rejecting loop for the word $ab^\omega$. But then an accepting state is visited at least once for $ab^nc$. By an induction argument, we can then show that for every $m \in \mathbb{N}$, a trace for $a(b^nc)^m$ needs to visit accepting states at least $m$ times. Similarly, a trace for $a(b^nc)^\omega$ visits an accepting state infinitely often, even though this word is not in $U^\omega$. Hence, the assumption that $U^\omega$ can be represented as a deterministic Büchi automaton is false.