# If the set of factors of an infinite word $\xi$ is regular, is this property stable under “shift's” of $\xi$?

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 Yuval Filmus 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

• I'm not quite sure this is research level. – Yuval Filmus Aug 9 '15 at 6:00
• @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 Aug 9 '15 at 8:33

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).

• 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 Aug 8 '15 at 21:53
• @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 Aug 8 '15 at 22:00
• 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 Aug 8 '15 at 22:15
• 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 Aug 9 '15 at 0:02
• @Stefan Your proof seems fine. So my idea doesn't work. It still remains to convert the counterexample to binary. – Yuval Filmus Aug 9 '15 at 5:59

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

• 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 Aug 9 '15 at 12:51
• The pumping lemma should work, no? – J.-E. Pin Aug 9 '15 at 14:09
• 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 Aug 9 '15 at 14:56
• @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 Jun 28 '16 at 0:33
• @GeorgZetzsche Thanks for the hint! His works looks interesting, I add a link to his homepage: igm.univ-mlv.fr/~tsmith – StefanH Jun 28 '16 at 14:05