<p>If $\xi$ is allowed to be ternary, I can give a counterexample; presumably a suitable binary encoding of $\xi$ would give a binary counterexample.</p>

<p>Let $(k_n)$ be some non-computable sequence, and let $(w_n)$ be a computable enumeration of all binary strings. Consider the word
$$ \xi = 1^{k_0} 0 w_0 1^{k_1} 0 w_1 1^{k_2} 0 w_2 \ldots $$
Clearly $T(\xi) = (0+1)^*$ is regular. On the other hand, $T(2\xi) = (0+1)^* + 2P(\xi)$, where $P(\xi)$ is the set of all prefixes of $\xi$. Since $(k_n)$ can be extracted from $P(\xi)$, we conclude that $T(2\xi)$ cannot be regular (or even computable).</p>

CC BY-SA 3.0
2015-08-08T21:53:28.740Z
Thank you! Do you have something to say about the other question, i.e. is $T(\xi/w)$ regular if $T(\xi)$ is regular? In that case I conjecture that this implication is true.
StefanH
CC BY-SA 3.0
2015-08-08T22:00:46.960Z
@Stefan I would imagine that a similar construction (this time binary) would show that the answer is still negative. I would try to emit a few words from the enumeration $(a_n)$. Let us know if this idea works out!
Yuval Filmus
CC BY-SA 3.0
2015-08-08T22:15:42.440Z
But $T(\xi/v) \subseteq T(\xi)$ for each prefix $v$ of $\xi$. So I do not see as how a similar construction would work, as it is based in some way on ''expanding'' $T(\xi)$ by this operation. Also my intuition tells me that if a have an automata for $T(\xi)$, then I can construct one for $T(\xi/v)$ by considering the states that are reached by $v$, then add an $\epsilon$-path from the start state to each such state. But I am unsure how to make this construction more formal and proof its correct.
StefanH
CC BY-SA 3.0
2015-08-09T00:02:25.713Z
Okay, I guess I found a proof that indeed if $T(\xi)$ is regular, $T(\xi/w)$ is regular too, but maybe I have overlooked something. I would greatly appreciate if you may take a look... just see the edit I made in my post for the proof.
StefanH
CC BY-SA 3.0
2015-08-09T05:59:29.210Z
@Stefan Your proof seems fine. So my idea doesn't work. It still remains to convert the counterexample to binary.
Yuval Filmus
CC BY-SA 3.0
2015-08-08T21:26:35.447Z
2015-08-08T21:26:35.447Z
Yuval Filmus
<p>Let $A = \{0,1\}$ be a binary alphabet and let $L = A^* -\{0,1\}^*00\{0,1\}^* = (01,1)^*(\varepsilon + 0)$. I denote by $F(w)$ the set of factors of a word $w$ and by $P(w)$ the set of its prefixes.</p>

<p>Let $w$ be an infinite word such that $F(1w) = L$ and $P(1w)$ is nonregular. Then $F(001w) = L \cup 00P(1w)$. Since $L$ is regular and do not intersect $00P(1w)$, $F(001w)$ is not regular. You can use Yuval's approach to give an explicit construction: take an enumeration $u_0, u_1, ...$ of $L$ and consider a word $1w = 1u_01^2u_1 \dotsm 1^nu_n \dotsm$.</p>

CC BY-SA 3.0
2015-08-09T12:51:54.457Z
Is there a simple argument that for $1w = 1u_01^2\cdots 1^n u_n \cdots$ the set $P(1w)$ is not regular, because contrary to Filmus the seq. $1,2,\ldots$ is computable? I found an argument using quotients, but maybe it is to complicated: the number of different $P(1w)/1u_0, \ldots, P(1w)/(1u_0\cdots 1^k u_{k-1}),\ldots$ is infinite, or $P(1w)/(1u_0\cdots 1^k u_{k-1}) = P(1w)/(1u_0\cdots 1^{k+i} u_{k+i-1})$ for some $k$ and all $i$. Hence as $1^{k+i} \in P(1w)/(1u_0\cdots 1^{k+i} u_{k+i-1})$ we have $1^{k+i} \in P(1w)/(1u_0\cdots 1^k u_{k-1})$ implying $1w = 1u_0\cdots 1^k u_{k-1}1^{\omega}$.
StefanH
CC BY-SA 3.0
2015-08-09T14:09:45.253Z
The pumping lemma should work, no?
J.-E. Pin
CC BY-SA 3.0
2015-08-09T14:56:47.797Z
Yes, and by the way discovered that if $P(\xi)$ is regular, then $\xi$ must be of the form $\xi = uw^{\omega}$ :) My proof: If $P(\xi)$ is regular, then there exists some $k > 0$ such that each prefix $u$ of length greather than $k$ could be decomposed as $u = xyz$ with $|xy| \le k, |y| \ge 1$ and such that $xy^iz \in P(\xi)$ for each $i \ge 0$. As $P(\xi)$ is prefix-closed we have $xy^i \in P(\xi)$ for all $i$, which implies $\xi = xy^{\omega}$, as the prefix sets determine an infinite word uniquely (we even have $P(\xi) \subseteq P(\eta)$ implies $\xi = \eta$, which was used here). Right?
StefanH
CC BY-SA 3.0
2016-06-28T00:33:43.590Z
@Stefan Questions like this (what does it mean for $\xi$ if $P(\xi)$ is from a particular language class) have been studied by Tim Smith in a recent series of papers. The fact that regular (or context-free) $P(\xi)$ implies that $\xi$ is ultimately periodic is the starting point of these considerations.
Georg Zetzsche
CC BY-SA 3.0
2016-06-28T14:05:49.207Z
@GeorgZetzsche Thanks for the hint! His works looks interesting, I add a link to his homepage: http://igm.univ-mlv.fr/~tsmith/
StefanH
CC BY-SA 3.0
2015-08-09T11:57:28.603Z
2015-08-09T11:57:28.603Z
J.-E. Pin
<p>Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w \cdot \eta = \xi$, i.e. the tail of $\xi$ after deleting the prefix $w$. Is it possible that for $\xi$ we have two prefixes $u,v$ of $\xi$ such that
$T(\xi/u)$ is regular, but $T(\xi/v)$ is not regular?</p>

<p>Closely related to this question is, if $w \in X^*$ and $\xi$ is an infinite sequence, is $T(w\cdot \xi)$ regular if $T(\xi)$ is regular, and if $w$ is a prefix, does $T(\xi)$ regular imply that $T(\xi/w)$ is regular?</p>

<p><strong>EDIT</strong>: I guess I have a proof that if $T(\xi)$ is regular, then $T(\xi/w)$ is regular too, but this is somewhat contrary to what Yuval Filmus wrote, so I would be grateful if someone would point out to me what might be wrong with my proof??</p>

<p>Okay, we introduce the notation $L / v := \{ u : vu \in L \}$ for $L \subseteq X^*$, the so called (right) quotient or derivative of $L$. First note that if $v$ is a prefix of $\xi$ then
$$
 T(\xi/v) = T(T(\xi)/v).
$$</p>

<blockquote>
  <p>Proof: If $w \in T(\xi/v)$ then we have $vxw\eta = \xi$ for some $x \in X^*$. So $vxw \in T(\xi)$ or $xw \in T(\xi) / v$, which shows $w \in T(T(\xi)/v)$. For the other inclusion let $w \in T(T(\xi)/v))$, then $xwy \in T(\xi)/v$ for some $x,y \in X^*$, and by definition $vxwy \in T(\xi)$. If $vxwy$ is a prefix of $\xi$, then $xwy$ is a prefix of $\xi/v$ and we have $xwy \in T(\xi)/v$ and hence $w \in T(\xi)/v$. If $vxwy$
  is not a prefix of $\xi$, then the part $xwy$ must occur in $\xi/v$, as it begins behind the $|v|$-th position in $\xi$, hence $xwy \in T(\xi)/v$ and so $w \in T(\xi)/v$.</p>
</blockquote>

<p>Okay, now the proof that $T(\xi)$ regular implies $T(\xi/w)$ is regular.</p>

<blockquote>
  <p>Proof: I use that if $L$ is regular, then its set of factors $T(L)$ is also regular (I guess this is true). Then if $T(\xi)$ is regular, then $T(\xi)/w$ is regular if $w$ is a prefix of $\xi$ as regular languages are closed under quotients (this could be found in many textbooks). Taken together
  $$
 T(\xi/w) = T(T(\xi)/w)
$$
  is regular, as it is the set of factors of the regular language $T(\xi)/w$. QED</p>
</blockquote>

CC BY-SA 3.0
2015-08-09T06:00:00.803Z
I'm not quite sure this is research level.
Yuval Filmus
CC BY-SA 3.0
2015-08-09T08:33:25.627Z
@YuvalFilmus: This result might not be publishable, but I think it is surprising that regularity is preserved by quotient but not by appending prefixes, despite that both operations are quite similar (they are inverse to each other in a certain sense and are sometimes called right and left shift). So it is at least above a simple exercise, and concerning the theoretical character I think it is more appropriate here than on cs.stackexchage.com. But tell me if you totally disagree.
StefanH
<fl.formal-languages><automata-theory>
If the set of factors of an infinite word $\xi$ is regular, is this property stable under "shift's" of $\xi$?
StefanH
# If the set of factors of an infinite word $\xi$ is regular, is this property stable under "shift's" of $\xi$?

(Asked by: username_0 on 2015-08-08)

Let $\xi$ be an infinite binary sequence, and denote by $T(\xi)$ the set of all factors (infixes) of $\xi$. Also if $w$ is some finite prefix of $\xi$, denote by $\xi/w$ the unique $\eta$ such that $w \cdot \eta = \xi$, i.e. the tail of $\xi$ after deleting the prefix $w$. Is it possible that for $\xi$ we have two prefixes $u,v$ of $\xi$ such that
$T(\xi/u)$ is regular, but $T(\xi/v)$ is not regular?

Closely related to this question is, if $w \in X^\*$ and $\xi$ is an infinite sequence, is $T(w\cdot \xi)$ regular if $T(\xi)$ is regular, and if $w$ is a prefix, does $T(\xi)$ regular imply that $T(\xi/w)$ is regular?

**EDIT**: I guess I have a proof that if $T(\xi)$ is regular, then $T(\xi/w)$ is regular too, but this is somewhat contrary to what username_1 wrote, so I would be grateful if someone would point out to me what might be wrong with my proof??

Okay, we introduce the notation $L / v := \{ u : vu \in L \}$ for $L \subseteq X^\*$, the so called (right) quotient or derivative of $L$. First note that if $v$ is a prefix of $\xi$ then
$$
T(\xi/v) = T(T(\xi)/v).
$$

> Proof: If $w \in T(\xi/v)$ then we have $vxw\eta = \xi$ for some $x \in X^\*$. So $vxw \in T(\xi)$ or $xw \in T(\xi) / v$, which shows $w \in T(T(\xi)/v)$. For the other inclusion let $w \in T(T(\xi)/v))$, then $xwy \in T(\xi)/v$ for some $x,y \in X^\*$, and by definition $vxwy \in T(\xi)$. If $vxwy$ is a prefix of $\xi$, then $xwy$ is a prefix of $\xi/v$ and we have $xwy \in T(\xi)/v$ and hence $w \in T(\xi)/v$. If $vxwy$
> is not a prefix of $\xi$, then the part $xwy$ must occur in $\xi/v$, as it begins behind the $|v|$-th position in $\xi$, hence $xwy \in T(\xi)/v$ and so $w \in T(\xi)/v$.

Okay, now the proof that $T(\xi)$ regular implies $T(\xi/w)$ is regular.

> Proof: I use that if $L$ is regular, then its set of factors $T(L)$ is also regular (I guess this is true). Then if $T(\xi)$ is regular, then $T(\xi)/w$ is regular if $w$ is a prefix of $\xi$ as regular languages are closed under quotients (this could be found in many textbooks). Taken together
> $$
> T(\xi/w) = T(T(\xi)/w)
> $$
> is regular, as it is the set of factors of the regular language $T(\xi)/w$. QED

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: I'm not quite sure this is research level.  
> **username_0**: @YuvalFilmus: This result might not be publishable, but I think it is surprising that regularity is preserved by quotient but not by appending prefixes, despite that both operations are quite similar (they are inverse to each other in a certain sense and are sometimes called right and left shift). So it is at least above a simple exercise, and concerning the theoretical character I think it is more appropriate here than on cs.stackexchage.com. But tell me if you totally disagree.  

---

## 2 answers

### Answer by username_1 on 2015-08-08. Score: 6 | Accepted answer

If $\xi$ is allowed to be ternary, I can give a counterexample; presumably a suitable binary encoding of $\xi$ would give a binary counterexample.

Let $(k\_n)$ be some non-computable sequence, and let $(w\_n)$ be a computable enumeration of all binary strings. Consider the word
$$ \xi = 1^{k\_0} 0 w\_0 1^{k\_1} 0 w\_1 1^{k\_2} 0 w\_2 \ldots $$
Clearly $T(\xi) = (0+1)^\*$ is regular. On the other hand, $T(2\xi) = (0+1)^\* + 2P(\xi)$, where $P(\xi)$ is the set of all prefixes of $\xi$. Since $(k\_n)$ can be extracted from $P(\xi)$, we conclude that $T(2\xi)$ cannot be regular (or even computable).

> **Comments:**
> **username_0**: Thank you! Do you have something to say about the other question, i.e. is $T(\xi/w)$ regular if $T(\xi)$ is regular? In that case I conjecture that this implication is true.  
> **username_1**: @Stefan I would imagine that a similar construction (this time binary) would show that the answer is still negative. I would try to emit a few words from the enumeration $(a_n)$. Let us know if this idea works out!  
> **username_0**: But $T(\xi/v) \subseteq T(\xi)$ for each prefix $v$ of $\xi$. So I do not see as how a similar construction would work, as it is based in some way on ''expanding'' $T(\xi)$ by this operation. Also my intuition tells me that if a have an automata for $T(\xi)$, then I can construct one for $T(\xi/v)$ by considering the states that are reached by $v$, then add an $\epsilon$-path from the start state to each such state. But I am unsure how to make this construction more formal and proof its correct.  
> **username_0**: Okay, I guess I found a proof that indeed if $T(\xi)$ is regular, $T(\xi/w)$ is regular too, but maybe I have overlooked something. I would greatly appreciate if you may take a look... just see the edit I made in my post for the proof.  
> **username_1**: @Stefan Your proof seems fine. So my idea doesn't work. It still remains to convert the counterexample to binary.  

---

### Answer by username_2 on 2015-08-09. Score: 7

Let $A = \{0,1\}$ be a binary alphabet and let $L = A^\* -\{0,1\}^\*00\{0,1\}^\* = (01,1)^\*(\varepsilon + 0)$. I denote by $F(w)$ the set of factors of a word $w$ and by $P(w)$ the set of its prefixes.

Let $w$ be an infinite word such that $F(1w) = L$ and $P(1w)$ is nonregular. Then $F(001w) = L \cup 00P(1w)$. Since $L$ is regular and do not intersect $00P(1w)$, $F(001w)$ is not regular. You can use Yuval's approach to give an explicit construction: take an enumeration $u\_0, u\_1, ...$ of $L$ and consider a word $1w = 1u\_01^2u\_1 \dotsm 1^nu\_n \dotsm$.

> **Comments:**
> **username_0**: Is there a simple argument that for $1w = 1u_01^2\cdots 1^n u_n \cdots$ the set $P(1w)$ is not regular, because contrary to Filmus the seq. $1,2,\ldots$ is computable? I found an argument using quotients, but maybe it is to complicated: the number of different $P(1w)/1u_0, \ldots, P(1w)/(1u_0\cdots 1^k u_{k-1}),\ldots$ is infinite, or $P(1w)/(1u_0\cdots 1^k u_{k-1}) = P(1w)/(1u_0\cdots 1^{k+i} u_{k+i-1})$ for some $k$ and all $i$. Hence as $1^{k+i} \in P(1w)/(1u_0\cdots 1^{k+i} u_{k+i-1})$ we have $1^{k+i} \in P(1w)/(1u_0\cdots 1^k u_{k-1})$ implying $1w = 1u_0\cdots 1^k u_{k-1}1^{\omega}$.  
> **username_2**: The pumping lemma should work, no?  
> **username_0**: Yes, and by the way discovered that if $P(\xi)$ is regular, then $\xi$ must be of the form $\xi = uw^{\omega}$ :) My proof: If $P(\xi)$ is regular, then there exists some $k > 0$ such that each prefix $u$ of length greather than $k$ could be decomposed as $u = xyz$ with $|xy| \le k, |y| \ge 1$ and such that $xy^iz \in P(\xi)$ for each $i \ge 0$. As $P(\xi)$ is prefix-closed we have $xy^i \in P(\xi)$ for all $i$, which implies $\xi = xy^{\omega}$, as the prefix sets determine an infinite word uniquely (we even have $P(\xi) \subseteq P(\eta)$ implies $\xi = \eta$, which was used here). Right?  
> **username_3**: @Stefan Questions like this (what does it mean for $\xi$ if $P(\xi)$ is from a particular language class) have been studied by Tim Smith in a recent series of papers. The fact that regular (or context-free) $P(\xi)$ implies that $\xi$ is ultimately periodic is the starting point of these considerations.  
> **username_0**: @GeorgZetzsche Thanks for the hint! His works looks interesting, I add a link to his homepage: http://igm.univ-mlv.fr/~tsmith/  

---

