# Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$: $$L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in L(\mathcal A) \}$$ where $v \sqsubset \eta$ means $v$ is a finite prefix of $\eta$ and $L(\mathcal A)$ denotes the finite (regular) language accepted by $\mathcal A$.

For $k > 0$ denote by $PF_k(\eta)$ the set of all $\omega$ words $\xi$ such that the first $k$ letters of $\eta$ and $\xi$ are the same (they share a common prefix of length $k$) and the infixes (or factors) of length $k$ are the same, i.e. if $F_k(\eta)$ denotes the factors of length $k$ then $PF_k(\eta) = \{ \xi : \eta[0...k] = \xi[0...k], F_k(\eta) = F_k(\xi) \}$.

Now I want to show, if $\eta \in L'(\mathcal A)$, then there exists a $k > 0$ such that $PF_k(\eta) \subseteq L'(A)$. First I thought that this does not hold, so that for every $\eta \in L'(A)$ and $k > 0$ you can find some $\xi \notin L'(A)$ such that $\xi \in PF_k(\eta)$, but didn't succeeded in constructing a counter-example, so I guess it holds but I have no idea how to proof it?

• Your observation regarding the emptiness of $L'(A)$ is incorrect. For example, if $L(A)=a^*+bb$, then $L'(A)=\{a^\omega\}$, but $bb\in L(A)$ and $b\notin L(A)$. – Shaull Oct 19 '13 at 18:19
• thank you for pointing out, I added "for sufficiently large words" because I think there exists some constant $n$ such that it holds for all $uv$ with $|uv| > n$, because if it is nonempty than there exists an infinite words of which all prefixes lie in $L(\mathcal A)$, and the set of prefixes of an infinite words certainly has this property. – StefanH Oct 19 '13 at 18:29
• I still don't think it's true. Consider $L(A)=a^*+(ab)^*$. Again, you have $L'(A)=\{a^\omega\}$, and $(ab)^n\in L(A)$, but not all its prefixes. – Shaull Oct 19 '13 at 19:31
• Ok, I was wrong, I deleted this claim. – StefanH Oct 19 '13 at 19:38
• Without the prefixes, I think that the answer would be negative. Take $L' = \{(ab)^\omega\}$. Then $(ba)^\omega$ has exactly the same factors as $(ab)^\omega$, but is not in $L'$. – J.-E. Pin Oct 20 '13 at 16:04

Let $$L$$ be the set of prefixes of $$(c^*ac^*b)^*$$.
Then $$L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$$.
Take the word $$\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$$.
For all $$k\in\mathbb N$$, we can show that $$PF_k(\eta)\not\subseteq L'$$, as witnessed by $$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\omega.$$
Indeed we have $$u_k\in PF_k(\eta)$$ but $$u_k\notin L'$$.