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?

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

The conjecture does not hold:

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


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.