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

• Aryeh: "The above reasoning is used in a paper without any further explanation" -- used in a different paper (please cite) or the paper by Han and Salomaa that you linked to?
• StefanH: Its a differenct paper: Complexity of Suffix-free Regular languages by J. Brzozoski and M. Szykula, and the question is related to Theorem 9 of this paper. The paper could be found here: arxiv.org/abs/1504.05159
• Aryeh: You could write to Brzozowski...
• StefanH: If nobody else can help here... but maybe would be better to have an answer here.
• Klaus Draeger: You already summarize the argument yourself; which step do you find unconvincing?

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