<p>If I had to do this in practice, I would use a SAT solver.</p>

<p>The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance.  For instance, one way is to have $2k^2$ boolean variables: $z_{s,b,t}$ is true if the DFA transitions from state $s$ to state $t$ on input bit $b$.  Then add some clauses to enforce that this is a DFA, and some variables and clauses to enforce that it accepts $x$ and rejects $y$.</p>

<p>Now use binary search on $k$ to find the smallest $k$ such that a DFA of this sort exists.  Based on what I've read in papers on related problem, I would expect that this might be reasonably effective in practice.</p>

<hr>

<p>Other encodings of this as SAT are possible.  For instance, we can use a trace encoding:</p>

<ul>
<li><p>If $x$ is of length $m$, you could add $m\lg k$ boolean variables: let $s_0,s_1,\dots,s_m$ be the sequence of states traversed on input $x$, and represent each $s_i$ using $\lceil \lg k \rceil$ boolean variables.</p></li>
<li><p>Now for each $i,j$ such that $x_i=x_j$, you have the constraint that $s_{i-1}=s_{j-1} \implies s_i=s_j$.</p></li>
<li><p>Next, extend this to handle $y$: let $t_0,\dots,t_n$ be the sequence of states traversed on input $y$, and represent each $t_j$ using $\lg k$ boolean variables.  For each $i,j$ such that $y_i=y_j$, add the constraint that $t_{i-1}=t_{j-1} \implies t_i=t_j$.</p></li>
<li><p>Similarly, for each $i,j$ such that $x_i=y_j$, add the constraint that $s_{i-1}=t_{j-1} \implies s_i=t_j$.</p></li>
<li><p>Both traces must start from the same starting point, so add the requirement that $s_0=t_0$ (WLOG you can require $s_0=t_0=0$).</p></li>
<li><p>To ensure that the DFA uses only $k$ states, require that $0 \le s_i &lt; k$ and $0 \le t_j &lt;k$ for all $i,j$.</p></li>
<li><p>Finally, to encode the requirement that $x$ is accepted and $y$ is rejected, require that $s_m \ne t_n$.</p></li>
</ul>

<p>All of these requirements can be encoded as SAT clauses.</p>

<p>As before, you'd use binary search on $k$ to find the smallest $k$ for which such a DFA exists.</p>

CC BY-SA 3.0
2015-01-14T18:25:01.950Z
note this will actually be superior to brute force search if there are certain symmetries in the problem and they are recognized by the solver, but can currently be difficult to identify/ isolate those (either for human or machine). there is also some newer/ related "technology" of [satisfiability modulo theories](http://en.wikipedia.org/wiki/Satisfiability_Modulo_Theories) and [answer set programming](http://en.wikipedia.org/wiki/Answer_set_programming) some of which has "built-in" graph predicates or can support their definitions.
vzn
CC BY-SA 3.0
2015-01-13T20:01:03.070Z
2015-01-13T20:01:03.070Z
D.W.
<p>Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y.  One way to do this is brute force search.  You enumerate DFA's starting with the smallest.  You try each DFA until you find one that accepts x and rejects y.</p>

<p>I want to know if there is any other known way of finding or building a minimum size DFA that accepts x and rejects y.  In other words, can we beat brute force search?</p>

<p>More Detail:</p>

<p>(1) I really do want an algorithm to find a minimum size DFA, not a near minimum size DFA.</p>

<p>(2) I don't just want to know how large or small the minimum DFA is.</p>

<p>(3) Right here, I'm only focused on the case were you have two strings x and y.</p>

<hr>

<p><strong>Edit</strong>:</p>

<p>Additional information for the interested reader:</p>

<p>Suppose $x$ and $y$ are binary strings of length at most $n$.  It is a known result that there is a DFA that accepts $x$ and rejects $y$ with at most $\sqrt{n}$ states.  Notice that there are about $n^{\sqrt{n}}$ DFA's with a binary alphabet and at most $\sqrt{n}$ states.  Therefore, the brute force approach wouldn't require us to enumerate through more than $n^{\sqrt{n}}$ DFA's.  It follows that the brute force approach couldn't take much more than $n^{\sqrt{n}}$ time.</p>

<p>Slides that I found helpful: <a href="https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf">https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf</a></p>

CC BY-SA 3.0
2015-01-12T19:13:24.230Z
I think I've heard of some learning approaches, but I'm not sure if they work for this specific case.  If you could explain one such approach, that would be quite helpful.
Michael Wehar
CC BY-SA 3.0
2015-01-12T20:45:09.107Z
@AndrásSalamon Is it still NP-complete if the sets to be distinguished each consist of only one string? It feels to me like this should be reasonably tractable.
mhum
CC BY-SA 3.0
2015-01-12T22:31:05.823Z
I didn't mention it in the question, but to the best of my knowledge, that's a possibility.  However, if x and y have length n, then it is known that there is a DFA with at most $\sqrt{n}$ states or less that accepts x and rejects y.  Therefore, the brute force search would give an answer in $2^{\sqrt{n}\log(\sqrt{n})}$ time or less.  Link: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf
Michael Wehar
CC BY-SA 3.0
2015-01-12T23:04:02.020Z
@MichaelWehar Is it insufficient to construct a simple non-minimal DFA that separates x and y and then run a standard DFA minimization algorithm? The simple non-minimal DFA can have $O(n)$ states (e.g.: if it's just based on the first differing character) and then [Hopcroft](http://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm) runs in $O(n log n)$.
mhum
CC BY-SA 3.0
2015-01-13T00:51:41.700Z
@mhum Small correction: it runs in $O(ns\cdot logn)$ where $s$ is the alphabet size. But this shouldn't change the running time in most cases.
Ryan Dougherty
CC BY-SA 3.0
2015-01-13T07:01:44.340Z
@mhum the problem that there are many different regular languages that separate the two strings — DFA minimization will find the best automaton for any one of these languages but will do nothing to compare it to automata for the other separating languages.
David Eppstein
CC BY-SA 3.0
2015-01-13T07:22:01.517Z
@DavidEppstein Ah yes. Of course.
mhum
CC BY-SA 3.0
2015-01-13T14:59:54.943Z
Do you want to do this in practice, or are you more interested in the theory (an algorithm with a provable bound on its worst-case running time)?  If you want to do this in practice, one approach is to use a SAT solver (this is one standard approach to finding a separating DFA).  If that's what you want, edit the question to say so and I'll add an answer elaborating.
D.W.
CC BY-SA 3.0
2015-01-13T19:03:34.367Z
@AndrásSalamon Hi, although I am not super familiar with the constructions, I believe Robson showed that you can separate any two bit strings of length n using a DFA with at most $n^{\frac{2}{5}}\log^{\frac{3}{5}}(n)$ states.  Although, this just gives us an upper bound on the size of the minimum DFA.  It doesn't really help us in constructing it.  That's why I didn't include references on this.
Michael Wehar
CC BY-SA 3.0
2015-01-13T19:04:48.683Z
@D.W. It would be nice to know the best approach in practice. Also, it would be nice to understand the complexity of this problem. But, the question I really want to answer right now is whether or not there is a known approach that always beats brute force search.
Michael Wehar
CC BY-SA 3.0
2015-01-13T21:09:52.193Z
If $x$ and $y$ are different lengths, with the larger of length $n$, it is easy to quickly find a DFA with $O(\log n)$ states that separates them:  just use a cycle of length $p$, where $p$ doesn't divide $|x|-|y|$.  Find $p$ by trying $2, 3, 5,\ldots$ in order until you find the appropriate $p$.  If $x$ and $y$ are the same length, then the $O(\sqrt{n})$ construction of Robson, in a 1996 paper, gives a simple machine that can be found by a search of size $O(n)$.  Neither construction is guaranteed to be the smallest DFA.
Jeffrey Shallit
CC BY-SA 3.0
2015-01-13T23:14:44.183Z
Shallit's notes, linked above, include the useful observation that the worst case for the separation problem is when the alphabet is binary: it's always possible to partition larger alphabets into two subsets that still distinguish the two input words and search for a binary automaton that treats letters in one subset as 0's and letters in the other subset as 1's. But for seeking the minimum separating automaton this doesn't seem to help, because you might be able to use the extra information from the original alphabet to do better than you could with a mapping to a binary alphabet.
David Eppstein
CC BY-SA 3.0
2015-01-14T04:05:24.647Z
a special case of this other recent question where in-set and out-set sizes equal 1. [minimal finite automata given in-words and out-words](http://cstheory.stackexchange.com/questions/27971/minimal-finite-automata-given-in-words-and-out-words). that answer lists some learning literature incl some heuristics.
vzn
CC BY-SA 3.0
2015-01-14T16:56:00.130Z
@AndrásSalamon Maybe I made a mistake?  But, I think there are only $2^{O(\sqrt{n}\log(\sqrt{n}))}$ DFA's with $\sqrt{n}$ states over a binary alphabet.  This is how I was counting them.  Label each state 1, 2, 3, ..., $\sqrt{n}$.  For each state i, we have to pick somewhere to transition on a 0 and somewhere to transition on a 1.  There are $\sqrt{n}$ choices for each.  Therefore, we get $\sqrt{n}^{2\sqrt{n}}$ = $2^{O(\sqrt{n}\log(\sqrt{n}))}$.  If there is something wrong with this, please do let me know.
Michael Wehar
CC BY-SA 3.0
2015-01-15T00:09:56.960Z
@AndrásSalamon Hi again, I think you made a mistake there.  We make two choices per state and there are $\sqrt{n}$ many states.  Therefore, we make $2\sqrt{n}$ choices in total.  For each choice, there are $\sqrt{n}$ possibilities.
Michael Wehar
CC BY-SA 3.0
2015-01-15T00:11:03.260Z
@AndrásSalamon Another way of thinking about it is that for each state there are n many ways to make the two choices.  Therefore, we get $n^{\sqrt{n}}$.
Michael Wehar
CC BY-SA 3.0
2015-01-15T06:57:54.037Z
You are right, $n^\sqrt{n}$ makes sense.  Again, please do edit the question to include these useful facts so someone finding it doesn't have to unscramble a bunch of comments.
András Salamon
CC BY-SA 3.0
2015-01-16T22:36:42.880Z
@AndrásSalamon Ok, cool.  Thanks again for your comments.  :)
Michael Wehar
CC BY-SA 3.0
2015-04-14T15:05:45.437Z
this seems not to be cited yet, the Shallit slides are connected to this paper coauthored by him. [Remarks on Separating Words](http://erikdemaine.org/papers/WordSep_DFCS2011/paper.pdf) / Demaine, Eisenstat, Shallit, Wilson
vzn
CC BY-SA 3.0
2015-04-14T16:20:48.047Z
@vzn Thanks!  I also found this paper to be quite relevant and interesting: http://drops.dagstuhl.de/opus/volltexte/2014/4854/pdf/30.pdf
Michael Wehar
CC BY-SA 3.0
2015-04-21T04:46:43.767Z
It's on counting which is somewhat related to separating words.  :)
Michael Wehar
<automata-theory><dfa><fsm>
Finding the smallest DFA that separates two words without using brute force search?
Michael Wehar
# Finding the smallest DFA that separates two words without using brute force search?

(Asked by: username_0 on 2015-01-12)

Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y. One way to do this is brute force search. You enumerate DFA's starting with the smallest. You try each DFA until you find one that accepts x and rejects y.

I want to know if there is any other known way of finding or building a minimum size DFA that accepts x and rejects y. In other words, can we beat brute force search?

More Detail:

(1) I really do want an algorithm to find a minimum size DFA, not a near minimum size DFA.

(2) I don't just want to know how large or small the minimum DFA is.

(3) Right here, I'm only focused on the case were you have two strings x and y.

---

**Edit**:

Additional information for the interested reader:

Suppose $x$ and $y$ are binary strings of length at most $n$. It is a known result that there is a DFA that accepts $x$ and rejects $y$ with at most $\sqrt{n}$ states. Notice that there are about $n^{\sqrt{n}}$ DFA's with a binary alphabet and at most $\sqrt{n}$ states. Therefore, the brute force approach wouldn't require us to enumerate through more than $n^{\sqrt{n}}$ DFA's. It follows that the brute force approach couldn't take much more than $n^{\sqrt{n}}$ time.

Slides that I found helpful: <https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf>

**Tags:** automata-theory, dfa, fsm

> **Comments:**
> **username_0**: I think I've heard of some learning approaches, but I'm not sure if they work for this specific case.  If you could explain one such approach, that would be quite helpful.  
> **username_1**: @AndrásSalamon Is it still NP-complete if the sets to be distinguished each consist of only one string? It feels to me like this should be reasonably tractable.  
> **username_0**: I didn't mention it in the question, but to the best of my knowledge, that's a possibility.  However, if x and y have length n, then it is known that there is a DFA with at most $\sqrt{n}$ states or less that accepts x and rejects y.  Therefore, the brute force search would give an answer in $2^{\sqrt{n}\log(\sqrt{n})}$ time or less.  Link: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf  
> **username_1**: @MichaelWehar Is it insufficient to construct a simple non-minimal DFA that separates x and y and then run a standard DFA minimization algorithm? The simple non-minimal DFA can have $O(n)$ states (e.g.: if it's just based on the first differing character) and then [Hopcroft](http://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm) runs in $O(n log n)$.  
> **username_2**: @username_1 Small correction: it runs in $O(ns\cdot logn)$ where $s$ is the alphabet size. But this shouldn't change the running time in most cases.  
> **username_3**: @username_1 the problem that there are many different regular languages that separate the two strings — DFA minimization will find the best automaton for any one of these languages but will do nothing to compare it to automata for the other separating languages.  
> **username_1**: @DavidEppstein Ah yes. Of course.  
> **username_4**: Do you want to do this in practice, or are you more interested in the theory (an algorithm with a provable bound on its worst-case running time)?  If you want to do this in practice, one approach is to use a SAT solver (this is one standard approach to finding a separating DFA).  If that's what you want, edit the question to say so and I'll add an answer elaborating.  
> **username_0**: @AndrásSalamon Hi, although I am not super familiar with the constructions, I believe Robson showed that you can separate any two bit strings of length n using a DFA with at most $n^{\frac{2}{5}}\log^{\frac{3}{5}}(n)$ states.  Although, this just gives us an upper bound on the size of the minimum DFA.  It doesn't really help us in constructing it.  That's why I didn't include references on this.  
> **username_0**: @username_4 It would be nice to know the best approach in practice. Also, it would be nice to understand the complexity of this problem. But, the question I really want to answer right now is whether or not there is a known approach that always beats brute force search.  
> **username_5**: If $x$ and $y$ are different lengths, with the larger of length $n$, it is easy to quickly find a DFA with $O(\log n)$ states that separates them:  just use a cycle of length $p$, where $p$ doesn't divide $|x|-|y|$.  Find $p$ by trying $2, 3, 5,\ldots$ in order until you find the appropriate $p$.  If $x$ and $y$ are the same length, then the $O(\sqrt{n})$ construction of Robson, in a 1996 paper, gives a simple machine that can be found by a search of size $O(n)$.  Neither construction is guaranteed to be the smallest DFA.  
> **username_3**: Shallit's notes, linked above, include the useful observation that the worst case for the separation problem is when the alphabet is binary: it's always possible to partition larger alphabets into two subsets that still distinguish the two input words and search for a binary automaton that treats letters in one subset as 0's and letters in the other subset as 1's. But for seeking the minimum separating automaton this doesn't seem to help, because you might be able to use the extra information from the original alphabet to do better than you could with a mapping to a binary alphabet.  
> **username_6**: a special case of this other recent question where in-set and out-set sizes equal 1. [minimal finite automata given in-words and out-words](http://cstheory.stackexchange.com/questions/27971/minimal-finite-automata-given-in-words-and-out-words). that answer lists some learning literature incl some heuristics.  
> **username_0**: @AndrásSalamon Maybe I made a mistake?  But, I think there are only $2^{O(\sqrt{n}\log(\sqrt{n}))}$ DFA's with $\sqrt{n}$ states over a binary alphabet.  This is how I was counting them.  Label each state 1, 2, 3, ..., $\sqrt{n}$.  For each state i, we have to pick somewhere to transition on a 0 and somewhere to transition on a 1.  There are $\sqrt{n}$ choices for each.  Therefore, we get $\sqrt{n}^{2\sqrt{n}}$ = $2^{O(\sqrt{n}\log(\sqrt{n}))}$.  If there is something wrong with this, please do let me know.  
> **username_0**: @AndrásSalamon Hi again, I think you made a mistake there.  We make two choices per state and there are $\sqrt{n}$ many states.  Therefore, we make $2\sqrt{n}$ choices in total.  For each choice, there are $\sqrt{n}$ possibilities.  
> **username_0**: @AndrásSalamon Another way of thinking about it is that for each state there are n many ways to make the two choices.  Therefore, we get $n^{\sqrt{n}}$.  
> **username_7**: You are right, $n^\sqrt{n}$ makes sense.  Again, please do edit the question to include these useful facts so someone finding it doesn't have to unscramble a bunch of comments.  
> **username_0**: @AndrásSalamon Ok, cool.  Thanks again for your comments.  :)  
> **username_6**: this seems not to be cited yet, the Shallit slides are connected to this paper coauthored by him. [Remarks on Separating Words](http://erikdemaine.org/papers/WordSep_DFCS2011/paper.pdf) / Demaine, Eisenstat, Shallit, Wilson  
> **username_0**: @username_6 Thanks!  I also found this paper to be quite relevant and interesting: http://drops.dagstuhl.de/opus/volltexte/2014/4854/pdf/30.pdf  
> **username_0**: It's on counting which is somewhat related to separating words.  :)  

---

## 1 answers

### Answer by username_4 on 2015-01-13. Score: 11 | Accepted answer

If I had to do this in practice, I would use a SAT solver.

The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance. For instance, one way is to have $2k^2$ boolean variables: $z\_{s,b,t}$ is true if the DFA transitions from state $s$ to state $t$ on input bit $b$. Then add some clauses to enforce that this is a DFA, and some variables and clauses to enforce that it accepts $x$ and rejects $y$.

Now use binary search on $k$ to find the smallest $k$ such that a DFA of this sort exists. Based on what I've read in papers on related problem, I would expect that this might be reasonably effective in practice.

---

Other encodings of this as SAT are possible. For instance, we can use a trace encoding:

* If $x$ is of length $m$, you could add $m\lg k$ boolean variables: let $s\_0,s\_1,\dots,s\_m$ be the sequence of states traversed on input $x$, and represent each $s\_i$ using $\lceil \lg k \rceil$ boolean variables.
* Now for each $i,j$ such that $x\_i=x\_j$, you have the constraint that $s\_{i-1}=s\_{j-1} \implies s\_i=s\_j$.
* Next, extend this to handle $y$: let $t\_0,\dots,t\_n$ be the sequence of states traversed on input $y$, and represent each $t\_j$ using $\lg k$ boolean variables. For each $i,j$ such that $y\_i=y\_j$, add the constraint that $t\_{i-1}=t\_{j-1} \implies t\_i=t\_j$.
* Similarly, for each $i,j$ such that $x\_i=y\_j$, add the constraint that $s\_{i-1}=t\_{j-1} \implies s\_i=t\_j$.
* Both traces must start from the same starting point, so add the requirement that $s\_0=t\_0$ (WLOG you can require $s\_0=t\_0=0$).
* To ensure that the DFA uses only $k$ states, require that $0 \le s\_i < k$ and $0 \le t\_j
* Finally, to encode the requirement that $x$ is accepted and $y$ is rejected, require that $s\_m \ne t\_n$.

All of these requirements can be encoded as SAT clauses.

As before, you'd use binary search on $k$ to find the smallest $k$ for which such a DFA exists.

> **Comments:**
> **username_6**: note this will actually be superior to brute force search if there are certain symmetries in the problem and they are recognized by the solver, but can currently be difficult to identify/ isolate those (either for human or machine). there is also some newer/ related "technology" of [satisfiability modulo theories](http://en.wikipedia.org/wiki/Satisfiability_Modulo_Theories) and [answer set programming](http://en.wikipedia.org/wiki/Answer_set_programming) some of which has "built-in" graph predicates or can support their definitions.  

---

