<p>The conjecture does not hold:</p>
<p>Let <span class="math-container">$L$</span> be the set of prefixes of <span class="math-container">$(c^*ac^*b)^*$</span>.</p>
<p>Then <span class="math-container">$L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$</span>.</p>
<p>Take the word <span class="math-container">$\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$</span>.</p>
<p>For all <span class="math-container">$k\in\mathbb N$</span>, we can show that <span class="math-container">$PF_k(\eta)\not\subseteq L'$</span>, as witnessed by <span class="math-container">$$u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\omega.$$</span></p>
<p>Indeed we have <span class="math-container">$u_k\in PF_k(\eta)$</span> but <span class="math-container">$u_k\notin L'$</span>.</p>

CC BY-SA 4.0
2020-07-07T20:26:42.323Z
2020-07-07T20:26:42.323Z
Denis
<p>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$. </p>

<p>For $k &gt; 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) \}$.</p>

<p>Now I want to show, if $\eta \in L'(\mathcal A)$, then there exists a $k &gt; 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 &gt; 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?</p>

CC BY-SA 3.0
2013-10-19T18:19:40.353Z
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
CC BY-SA 3.0
2013-10-19T18:29:25.073Z
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
CC BY-SA 3.0
2013-10-19T19:31:12.980Z
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
CC BY-SA 3.0
2013-10-19T19:38:04.763Z
Ok, I was wrong, I deleted this claim.
StefanH
CC BY-SA 3.0
2013-10-19T21:37:25.470Z
Is there a reason that you require the prefixes of length $k$ to be equal in $PF_\kappa(\eta)$?  What happens if you remove this requirement?
nickie
CC BY-SA 3.0
2013-10-19T22:09:53.107Z
@nickie: my initial thought was that it would be easier to proof the existence of an $k > 0$ such that $PF_k(\eta) \subseteq L'(\mathcal A)$ when the prefixes are also required to be common, because then maybe more could be said about the infixes that appear in an word if I know it has a specified prefix, but that was just an intuitive thought, if you know some similar results without this requirement I would be glad if you share...
StefanH
CC BY-SA 3.0
2013-10-20T16:04:53.717Z
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
<fl.formal-languages><automata-theory><regular-language><omega-language>
Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata
StefanH
# Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

(Asked by: username_0 on 2013-10-19)

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?

**Tags:** fl.formal-languages, automata-theory, regular-language, omega-language

> **Comments:**
> **username_1**: 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)$.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Ok, I was wrong, I deleted this claim.  
> **username_2**: Is there a reason that you require the prefixes of length $k$ to be equal in $PF_\kappa(\eta)$?  What happens if you remove this requirement?  
> **username_0**: @username_2: my initial thought was that it would be easier to proof the existence of an $k > 0$ such that $PF_k(\eta) \subseteq L'(\mathcal A)$ when the prefixes are also required to be common, because then maybe more could be said about the infixes that appear in an word if I know it has a specified prefix, but that was just an intuitive thought, if you know some similar results without this requirement I would be glad if you share...  
> **username_3**: 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'$.  

---

## 1 answers

### Answer by username_4 on 2020-07-07. Score: 2 | Accepted answer

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


---

