0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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