<p>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\}$. </p>

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

CC BY-SA 3.0
2016-12-11T17:29:10.127Z
2016-12-11T17:29:10.127Z
StefanH
<p>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 (<a href="https://arxiv.org/abs/1504.05159" rel="nofollow noreferrer">https://arxiv.org/abs/1504.05159</a>).</p>

CC BY-SA 3.0
2016-12-13T19:03:52.090Z
2016-12-13T19:03:52.090Z
MarekSz
<p>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$.</p>

<p>That such languages exist is shown in <a href="http://www.sciencedirect.com/science/article/pii/S0304397508008815" rel="nofollow">this paper</a>. 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$.</p>

CC BY-SA 3.0
2016-08-31T19:55:14.003Z
"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?
Aryeh
CC BY-SA 3.0
2016-08-31T19:57:14.847Z
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: http://arxiv.org/abs/1504.05159
StefanH
CC BY-SA 3.0
2016-08-31T20:21:23.377Z
You could write to Brzozowski...
Aryeh
CC BY-SA 3.0
2016-08-31T21:52:10.087Z
If nobody else can help here... but maybe would be better to have an answer here.
StefanH
CC BY-SA 3.0
2016-09-01T20:50:36.490Z
You already summarize the argument yourself; which step do you find unconvincing?
Klaus Draeger
CC BY-SA 3.0
2016-09-02T09:03:01.557Z
@KlausDraeger Why does $\delta_R(F, w) = S$ implies that we have *the same* $r \in F$ such that $\delta(p, w^R) = r = \delta(q, w^R)$, I do not see that, just that we have some (possible different) elements from $F$ that get mapped to $p$ and $q$ by $w$? But why just one element?
StefanH
<co.combinatorics><fl.formal-languages><automata-theory><regular-language>
A property of suffix-free regular languages of maximal state complexity for the reverse operation
StefanH
# A property of suffix-free regular languages of maximal state complexity for the reverse operation

(Asked by: username_0 on 2016-08-31)

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](http://www.sciencedirect.com/science/article/pii/S0304397508008815). 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$.

**Tags:** co.combinatorics, fl.formal-languages, automata-theory, regular-language

> **Comments:**
> **username_1**: "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?  
> **username_0**: 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: http://arxiv.org/abs/1504.05159  
> **username_1**: You could write to Brzozowski...  
> **username_0**: If nobody else can help here... but maybe would be better to have an answer here.  
> **username_2**: You already summarize the argument yourself; which step do you find unconvincing?  
> **username_0**: @KlausDraeger Why does $\delta_R(F, w) = S$ implies that we have *the same* $r \in F$ such that $\delta(p, w^R) = r = \delta(q, w^R)$, I do not see that, just that we have some (possible different) elements from $F$ that get mapped to $p$ and $q$ by $w$? But why just one element?  

---

## 2 answers

### Answer by username_0 on 2016-12-11. Score: 2 | Accepted answer

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


---

### Answer by username_3 on 2016-12-13. Score: 3

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


---

