2
$\begingroup$

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

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

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

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

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

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

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.