4
$\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$
7
  • $\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, 2013 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, 2013 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, 2013 at 19:31
  • $\begingroup$ Ok, I was wrong, I deleted this claim. $\endgroup$
    – StefanH
    Oct 19, 2013 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, 2013 at 16:04

1 Answer 1

2
$\begingroup$

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

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