A property of suffix-free regular languages of maximal state complexity for the reverse operation

Question

Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of the minimal automaton of $L$ which are neither the initial state nor a sink state, then there exists a word $w \in X^*$ such that $\delta(q, w) = \delta(p, w)$ in the minimal automaton for $L$.

That such languages exist is shown in this paper. The above reasoning is used in a paper without any further explanation, and I do not see that it is true. If we denote by $Q = \{0,\ldots, n-1\}$ the states of the minimal automaton of $L$ and by $F$ its final states, where $0$ is the start state and $n-1$ the sink state (which a suffix-free language always has) then it just precedes with constructing a NFA for $L^R$, determinizing by the subset construction and showing that it must contain the $2^{n-2}+1$ sets $\{ \{ 0 \} \}\cup \{ S \subseteq \{1,\ldots, n-2\}\}$ as states. Hence for $p,q \in \{1,\ldots, n-2\}$ we have some $p,q \in S$ such that $\delta_R(F, w) = S$ in the constructed automaton for $L^R$, and then it concludes that $\delta(p, w^R) = r = \delta(q, w^R)$ for some state $r$.

Answer 1

StefanH: You are right, there was this bug in the proof of Theorem 9 in the arxiv version; the argument worked only for $|F|=1$. We fixed this in the revised version for a journal (not published yet) in a similar way you proposed. I have just updated arxiv (https://arxiv.org/abs/1504.05159).

Answer 2

The conclusion that $\delta(p, w^R) = \delta(q, w^R)$ does not seem to hold; but for the argument used in the proof of the paper this is not necessary. More specifically, in the paper it is enough that for every distinct $p,q \in \{1,\ldots, n-2\}$ there is no word $u$ such that $\delta(0, u) = p, \delta(r, u) = q$ for some $r \in \{1,\ldots, n-2\}$.

Suppose the above holds for two $p,q \in \{1,\ldots, n-2\}$ distinct, then as written in the post we have some $S$ with $p,q \in S$ and a word $w$ such that $\delta(F, w) = S$, which gives $\delta(p, w^R) \in F, \delta(q, w^R) \in F$. But then $uw^R \in L$ and furthermore as the automaton is minimal, we have some word $v$ such that $\delta(0,v) = r$, hence $vuw^R \in L$, contradicting the suffix-freeness of $L$.