4
$\begingroup$

Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words:

The automata accepts $\xi \in X^{\omega}$ with respect to $F$ iff $$ \forall i : \delta(q_0, \xi[0...i]) \in F. $$ Meaning that every prefix $\xi[0...i]$ of $\xi$ goes to an acceptance state. With $L'(\mathcal A)$ I denote the set of all accepted infinite words.

Now such automata have a special form, a word is accepted iff it just passes through certain allowed states in $F$, otherwise it is rejected if it ever enters a state from $Q\setminus F$. This by the way means that if $\mathcal A$ is reduced and complete, it has exactly one non-accepting trapping state $s$, because every word which enters $s$ needs to ultimately stay there, because the word gets never accepted, regardless of what comes there after $s$ was entered.

Now I define $F_n(\xi) := \{ w \in X^* : w \in \mbox{infix}(\xi) \cap X^n \}$, the set of all factors (or infixes) of $\xi$ of length $n$. Then $$K_n(\xi) := \xi[0...n] \cdot X^{\omega} \cap \{ \eta \in X^{\omega} : F_n(\eta) = F_n(\xi) \}$$ is the set of all infinite words which share with $\xi$ a common prefix of length $n$ and which have the same set of factors of length $n$.

Now I conjecture: If $\xi$ is accepted by $\mathcal A$ according to the above mentioned acceptance condition, then there exists a $n > 0$ such that $$ K_n(\xi) \subseteq L'(\mathcal A) $$ meaning that if $\xi$ is accepted there exists a $n > 0$ such that every word which share with $\xi$ a common prefix of length $n$ and all factors of length $n$ (and up to $n$) is also accepted.

Intuitively I guess this is right, because if $\xi$ is accepted, and because $\mathcal A$ is a finite automata, then as $\xi$ goes through the states it eventually ends in some cycle, which I guesss bound the possible factors, and the prefix condition could be used to ensure that another word would end in the same cycle.

If $\xi = uv^{\omega}$ for finite $u, v$, i.e. if $\xi$ is ultimately periodic I guess a construction would be to determine the smallest $k$ such that $F_k(\xi) = F_{k+1}(\xi)$, so the number of factors of length $k' > k$ is the same as $|F_k(\xi)|$, and set $n := k + 1$. Then I conjecture $$ K_{n}(\xi) \subseteq L'(\mathcal A). $$ (I have no proof) Maybe this works also for non-ultimately periodic words, but I could not proof it. So any ideas? Or maybe an idea how to proof my conjecture?

$\endgroup$
1
  • $\begingroup$ +1. This is a very nice question. $\endgroup$ Oct 28, 2013 at 15:10

1 Answer 1

3
$\begingroup$

Your first conjecture — the claim that does not insist on eventually periodic input — is not true.

For a counterexample, consider the language consisting of all infinite binary strings $\xi$, such that every infix maximal finite block of $0$s has even length. This language can be accepted by a machine according to your criterion, since we can design an automata that when reading a $0$ toggles between two (accepting) states to check the parity, and if you have a $1$ from the odd state, you go to a rejecting state, but a $1$ from the even state returns to the even state. Any infinite string with an odd block will reach that rejecting state, but strings with only even blocks will always be in the acceptable states.

Now, let $\xi$ be a string with arbitrarily long even-length blocks of $0$s, separated by individual $1$s. For example, $\xi=11001000010000001\cdots$. I claim that there is no $n$ for which your desired property holds. Fix any $n$, and let $\eta$ be obtained from $\xi$ by inserting an extra $0$ into one of the very long blocks of $0$s in $\xi$, well beyond $n$. Since the affected block was very long, it follows that $\eta$ and $\xi$ have exactly the same infix strings of length $n$, and they agree on their first $n$ characters. But $\xi$ was accepted and $\eta$ will be rejected.

In the case of eventually periodic input, however, I claim that the conjecture is correct. Suppose the input $\xi=uv^\omega$ is eventually periodic. Let $n$ be extremely large in comparison with the lengths of $u$ and $v$. Now, I claim that any string $\eta$ that starts with $u$ and has the same length $n$ infix strings as $\xi$, must in fact be equal to $\xi$. The reason is that $\eta$ must begin with something like $uv^k$, and if it subsequently deviates from $\xi$, then this deviation will be at the end of a length $n$ string that does not arise in $\xi$. (Please correct me if this is mistaken.) By using this $n$, we attain your desired criterion trivially, since the only string $\eta$ involved is $\xi$ itself, which is in the language.

$\endgroup$

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.