3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Shaull Oct 19 '13 at 18:19
  • $\begingroup$ 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. $\endgroup$ – StefanH Oct 19 '13 at 18:29
  • $\begingroup$ 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. $\endgroup$ – Shaull Oct 19 '13 at 19:31
  • $\begingroup$ Ok, I was wrong, I deleted this claim. $\endgroup$ – StefanH Oct 19 '13 at 19:38
  • 2
    $\begingroup$ 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'$. $\endgroup$ – J.-E. Pin Oct 20 '13 at 16:04

Your Answer

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

Browse other questions tagged or ask your own question.