7
$\begingroup$

Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-Automaton, equivalently if it is of the form $$ L = \bigcup_i^n U_i V_i^{\omega} $$ for regular languages $U_i, V_i$ in the usual sense, also $L$ is regular iff it is acceptable by a Müller-Automata (see Wikipedia).

Let $\xi \in X^{\omega}$ be some infinite word, denote by $A(\xi)$ the set of its prefixes, these are finite words and so $A(\xi) \subseteq X^*$, likewise define $F(\xi)$ to be the set of factors of $\xi$.

Now define the following language operator (called adherence) on $X^{\omega}$: $$ \mbox{Adh}(L) := \{ \xi \in X^{\omega} : A(\xi) \subseteq A(L) \}. $$ It is $\xi \in \mbox{Adh}(L)$ iff every prefix of $\xi$ is the prefix of some word from $L$. Now if $L$ is $\omega$-regular, $A(\xi)$ is $\omega$ regular too, if given a Büchi-Automata for $L$ just declare every state on an acceptance path (i.e. a path having an infinite number of final states) a final state too, the automata with the usual acceptance condition for finite words accepts $A(\xi)$. Now $\mbox{Adh}(L)$ is accepted by this automaton according to the Büchi-condition.

I want to generalise this, define the operator $$ \mbox{Adh}_F(L) = \{ \xi \in X^{\omega} : F(\xi) \subseteq F(L). $$ It is $\xi \in \mbox{Adh}_F(L)$ iff every factor of $\xi$ is a factor of some word from $L$. Now I want to know

If $L$ is $\omega$-regular, is $\mbox{Adh}_F(L)$ also $\omega$-regular?

I conjecture that in general not to be true, because to test an infinite word $\xi$ for this condition, if the automaton would read the $n$-te symbol, it need to trace back to to all the position $1,2,\ldots, n$ of $\xi$ and test from them if the factor starting at this position and ending at the $n$-th position is contained in $F(L)$, but in general a finite automata can not save the last $n$-th positions for abitrary $n$.

On the other side I am not able to represent some known non-regular languages as $\mbox{Adh}_F(L)$, and furthermore for a regular set $L$ the set $F(L)$ is regular too (given an automata for $L$ on every path which is final, i.e. leads to a final state, put an $\varepsilon$-transition from the start state to that state). So maybe I have overlooked some property of factor sets which make $\mbox{Adh}_F$ regular...

$\endgroup$
3
$\begingroup$

Then answer is yes. Since $F(L)$ is a regular language, it suffices to prove the following result:

If $K$ is a regular language, then $R(K) = \{u \in A^\omega \mid F(u) \subseteq K \}$ is $\omega$-regular.

Since regular languages are closed under complement, it suffices to show that $R(K^c)$ is $\omega$-regular. Observing that $R(K^c) = \{u \in A^\omega \mid F(u) \subseteq K^c \}$, we get $$ (R(K^c))^c = \{u \in A^\omega \mid F(u) \cap K \not= \emptyset \} = A^*KA^\omega $$ Thus $(R(K^c))^c$ is $\omega$-regular, and since $\omega$-regular languages are closed under complement, $R(K^c)$ is $\omega$-regular.

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