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$
2
  • 3
    $\begingroup$ I'm not quite sure this is research level. $\endgroup$ Commented Aug 9, 2015 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
    Commented Aug 9, 2015 at 8:33

2 Answers 2

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$
5
  • $\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
    Commented Aug 8, 2015 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$ Commented Aug 8, 2015 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
    Commented Aug 8, 2015 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
    Commented Aug 9, 2015 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$ Commented Aug 9, 2015 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$
5
  • $\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
    Commented Aug 9, 2015 at 12:51
  • $\begingroup$ The pumping lemma should work, no? $\endgroup$
    – J.-E. Pin
    Commented Aug 9, 2015 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
    Commented Aug 9, 2015 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$ Commented Jun 28, 2016 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
    Commented Jun 28, 2016 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.