<p>this is apparently not a very well-studied problem in the sense of known/available algorithms other than the original/long-ago strategy of "determinize to DFA/minimize DFA". you seem to indicate the determinization step is the problematic one but this is typical of course given that it has an exponential-space/time worse case. note that there are several <a href="http://en.wikipedia.org/wiki/DFA_minimization" rel="nofollow noreferrer">DFA minimization algorithms</a> which can vary significantly in performance on average.</p>

<p>it is also known more informally as <a href="https://stackoverflow.com/questions/3379051/nfa-minimization-without-determinization">"NFA minimization without determinization"</a>. it is known to be hard in the sense that there are basically not even approximation algorithms unless P=Pspace as shown in this paper:</p>

<ul>
<li><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.5056" rel="nofollow noreferrer">Minimizing NFA's and Regular Expressions by Gregor Gramlich, Georg Schnitger</a></li>
</ul>

<p>however this paper does consider the generally rarely explored case of some algorithms that are not based on finding the determinized DFA 1<sup>st</sup>:</p>

<ul>
<li><a href="http://dl.acm.org/citation.cfm?id=1758106" rel="nofollow noreferrer">NFA reduction algorithms by means of regular inequalities</a> Jean-Marc Champarnaud, Fabien Coulon</li>
</ul>

<blockquote>
  <p>We present different techniques for reducing the number of states and transitions in nondeterministic automata. These techniques are based on the two preorders over the set of states, related to the inclusion of left and right languages. Since their exact computation is NP-hard, we focus on polynomial approximations which enable a reduction of the NFA all the same.</p>
</blockquote>

<p>note a publicly available package/implementation that can handle large NFA/DFA conversions/minimizations etc generally efficiently as possible is the <a href="http://en.wikipedia.org/wiki/AT%26T_FSM_Library" rel="nofollow noreferrer">AT&amp;T FSM library</a>.</p>

<p>it has a strategy <code>fsmcompact</code> which can sometimes suffice:</p>

<blockquote>
  <p>In cases where a transducer or weighted  acceptor  can  not  be  determinized  or grows very large, a different optimization may be useful —
         <code>fsmcompact</code>.  This operation encodes each triple of an input label, output  label  and  cost  into  a  single  new  label,  performs classical
         (unweighted  acceptor)  determinization  and  minimization,  and   then
         decodes  the  encoded  labels back into their original values. This has
         the advantage that it is always defined and that it does not move  output  labels  or  costs  along  paths.  It has the disadvantage that the
         result can be neither deterministic nor minimal.</p>
</blockquote>

CC BY-SA 3.0
2013-07-17T15:32:39.637Z
see also [On NFA reductions](http://www.csd.uwo.ca/faculty/ilie/TisF04.pdf) Ilie, Navarro, Yu
vzn
CC BY-SA 3.0
2013-07-16T23:23:04.247Z
2013-07-16T23:28:37.053Z
2017-05-23T12:40:09.333Z
vzn
<p>Have you tried <a href="https://en.wikipedia.org/wiki/DFA_minimization#Brzozowski.27s_algorithm">Brzozowski's algorithm</a>?  It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize.</p>

<p>The following paper seems relevant:</p>

<ul>
<li><a href="http://www.fc.up.pt/dcc/Pubs/TReports/TR07/dcc-2007-03.pdf">On the performance of automata minimization algorithms</a>, Marco Almeida, Nelma Moreira, Rogerio Reis.</li>
</ul>

<p>It evaluates a number of different algorithms for DFA minimization, including their application to your situation where we start with a NFA and want to convert it to a DFA and minimize it.</p>

<p>What does the strongly connected components (SCC) decomposition of your NFA (considering it as a directed graph) look like?  Does it have many components, where none of the components is too large?  If so, I wonder if it might be possible to devise a divide-and-conquer algorithm, where you take a single component, convert it from NFA to DFA and then minimize it, and then replace the original with the new determinized version.  This should be possible for single-entry components (where all edges into that component lead to a single vertex, the entry vertex).  I don't immediately see whether it would be possible to do something like this for arbitrary NFAs, but if you check what the structure of the SCC looks like, then you might be able to determine whether this sort of direction is worth exploring or not.</p>

CC BY-SA 3.0
2013-07-17T06:59:52.787Z
Brzozowski's algorithm seems promising, but the divide and conquer technique even more! In my case this is really easy to do and does not require large code changes. I will do that and if that works, I will accept your answer.
Jendas
CC BY-SA 3.0
2013-07-18T10:39:55.053Z
I came, I asked, I divided, I conquered
Jendas
CC BY-SA 3.0
2013-07-17T01:42:18.240Z
2013-07-17T01:47:41.240Z
2013-07-17T01:47:41.240Z
D.W.
<p>I have really large Non-deterministic finite automaton and I need to convert it to the DFA. </p>

<p>By large I mean 40 000+ states.
So far I have done some experiments and programmed the default algorithm that searches through table (as described <a href="http://www.youtube.com/watch?v=taClnxU-nao">here</a>), but even after optimization is quite slow and very memory consuming. I am aware of the fact, that the number of states can grow exponentially, but after minimization, the resulting DFA has about 9 000 states and that is bearable.</p>

<p>So my question is, is there some algorithm, that would be faster or more memory friendly? </p>

CC BY-SA 3.0
2013-07-16T23:05:44.607Z
the video is apparently on the standard determinizing algorithm. see eg [NFA minimization without determinization, stackoverflow](http://stackoverflow.com/questions/3379051/nfa-minimization-without-determinization)
vzn
CC BY-SA 3.0
2013-07-17T01:30:20.087Z
If you do the naive NFA->DFA conversion (using the product construction), how large is the resulting DFA?  (before minimization)
D.W.
CC BY-SA 3.0
2013-07-17T02:33:08.473Z
What do you you want to do with the DFA? If you are interested in inclusion checks, there are algorithms to do that directly.
Vijay D
CC BY-SA 3.0
2013-07-17T06:44:12.803Z
Thank you for very fast answers. For the size, I can not tell exactly since my RAM ran out, but I will give it closer look and than extend the question. For the what I want to do, I am not sure, whether I can openly chat about that, since it is a bit of my firm know-how. But I can surely state, that I actually need the resulting DFA.
Jendas
CC BY-SA 3.0
2013-07-17T16:40:16.350Z
Have you tried running Angluin's algorithm for learning DFAs from membership and equivalence queries? The membership part is easy (just run your DFA on the requisite string); for equivalence, you could draw lots of random strings or try all strings up to a certain length. This is only a heuristic as you'll never really know when you're done, but I've found that this trick works well in practice...
Aryeh
CC BY-SA 3.0
2013-07-18T06:11:39.917Z
"just run your DFA" should of course be "just run your NFA"
Aryeh
CC BY-SA 3.0
2013-07-18T08:05:32.797Z
Ok, that seems to be interesting but as I understand it, this approach brings great uncertainty. I have actually investigated this algorithm when working on different project and it is quite awesome but I do not think, that it would really help me here since I can not afford uncertainty.
Jendas
CC BY-SA 3.0
2014-11-04T21:59:44.160Z
Hi Jendas, I am looking for a large DFA/NFA to test an algorithm (regular expression matching) I am working on. Could you tell me more details on what kind of DFA are you using in your experiment?
sm13294
CC BY-SA 3.0
2014-11-05T08:25:21.957Z
Please do contact me via e-mail, which can be found on my profile, and I will happily provide you more details. :-)
Jendas
<dfa>
Algorithm for converting very large NFA to DFA
Jendas
# Algorithm for converting very large NFA to DFA

(Asked by: username_0 on 2013-07-16)

I have really large Non-deterministic finite automaton and I need to convert it to the DFA.

By large I mean 40 000+ states.
So far I have done some experiments and programmed the default algorithm that searches through table (as described [here](http://www.youtube.com/watch?v=taClnxU-nao)), but even after optimization is quite slow and very memory consuming. I am aware of the fact, that the number of states can grow exponentially, but after minimization, the resulting DFA has about 9 000 states and that is bearable.

So my question is, is there some algorithm, that would be faster or more memory friendly?

**Tags:** dfa
> **Comments:**
> **username_1**: the video is apparently on the standard determinizing algorithm. see eg [NFA minimization without determinization, stackoverflow](http://stackoverflow.com/questions/3379051/nfa-minimization-without-determinization)  
> **username_2**: If you do the naive NFA->DFA conversion (using the product construction), how large is the resulting DFA?  (before minimization)  
> **username_3**: What do you you want to do with the DFA? If you are interested in inclusion checks, there are algorithms to do that directly.  
> **username_0**: Thank you for very fast answers. For the size, I can not tell exactly since my RAM ran out, but I will give it closer look and than extend the question. For the what I want to do, I am not sure, whether I can openly chat about that, since it is a bit of my firm know-how. But I can surely state, that I actually need the resulting DFA.  
> **username_4**: Have you tried running Angluin's algorithm for learning DFAs from membership and equivalence queries? The membership part is easy (just run your DFA on the requisite string); for equivalence, you could draw lots of random strings or try all strings up to a certain length. This is only a heuristic as you'll never really know when you're done, but I've found that this trick works well in practice...  
> **username_4**: "just run your DFA" should of course be "just run your NFA"  
> **username_0**: Ok, that seems to be interesting but as I understand it, this approach brings great uncertainty. I have actually investigated this algorithm when working on different project and it is quite awesome but I do not think, that it would really help me here since I can not afford uncertainty.  
> **username_5**: Hi Jendas, I am looking for a large DFA/NFA to test an algorithm (regular expression matching) I am working on. Could you tell me more details on what kind of DFA are you using in your experiment?  
> **username_0**: Please do contact me via e-mail, which can be found on my profile, and I will happily provide you more details. :-)  

---

## 2 answers

### Answer by username_2 on 2013-07-17. Score: 6 | Accepted answer

Have you tried [Brzozowski's algorithm](https://en.wikipedia.org/wiki/DFA_minimization#Brzozowski.27s_algorithm)? It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize.

The following paper seems relevant:

* [On the performance of automata minimization algorithms](http://www.fc.up.pt/dcc/Pubs/TReports/TR07/dcc-2007-03.pdf), Marco Almeida, Nelma Moreira, Rogerio Reis.

It evaluates a number of different algorithms for DFA minimization, including their application to your situation where we start with a NFA and want to convert it to a DFA and minimize it.

What does the strongly connected components (SCC) decomposition of your NFA (considering it as a directed graph) look like? Does it have many components, where none of the components is too large? If so, I wonder if it might be possible to devise a divide-and-conquer algorithm, where you take a single component, convert it from NFA to DFA and then minimize it, and then replace the original with the new determinized version. This should be possible for single-entry components (where all edges into that component lead to a single vertex, the entry vertex). I don't immediately see whether it would be possible to do something like this for arbitrary NFAs, but if you check what the structure of the SCC looks like, then you might be able to determine whether this sort of direction is worth exploring or not.

> **Comments:**
> **username_0**: Brzozowski's algorithm seems promising, but the divide and conquer technique even more! In my case this is really easy to do and does not require large code changes. I will do that and if that works, I will accept your answer.  
> **username_0**: I came, I asked, I divided, I conquered  

---

### Answer by username_1 on 2013-07-16. Score: 2

this is apparently not a very well-studied problem in the sense of known/available algorithms other than the original/long-ago strategy of "determinize to DFA/minimize DFA". you seem to indicate the determinization step is the problematic one but this is typical of course given that it has an exponential-space/time worse case. note that there are several [DFA minimization algorithms](http://en.wikipedia.org/wiki/DFA_minimization) which can vary significantly in performance on average.

it is also known more informally as ["NFA minimization without determinization"](https://stackoverflow.com/questions/3379051/nfa-minimization-without-determinization). it is known to be hard in the sense that there are basically not even approximation algorithms unless P=Pspace as shown in this paper:

* [Minimizing NFA's and Regular Expressions by Gregor Gramlich, Georg Schnitger](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.5056)

however this paper does consider the generally rarely explored case of some algorithms that are not based on finding the determinized DFA 1st:

* [NFA reduction algorithms by means of regular inequalities](http://dl.acm.org/citation.cfm?id=1758106) Jean-Marc Champarnaud, Fabien Coulon

> We present different techniques for reducing the number of states and transitions in nondeterministic automata. These techniques are based on the two preorders over the set of states, related to the inclusion of left and right languages. Since their exact computation is NP-hard, we focus on polynomial approximations which enable a reduction of the NFA all the same.

note a publicly available package/implementation that can handle large NFA/DFA conversions/minimizations etc generally efficiently as possible is the [AT&T FSM library](http://en.wikipedia.org/wiki/AT%26T_FSM_Library).

it has a strategy `fsmcompact` which can sometimes suffice:

> In cases where a transducer or weighted acceptor can not be determinized or grows very large, a different optimization may be useful —
> `fsmcompact`. This operation encodes each triple of an input label, output label and cost into a single new label, performs classical
> (unweighted acceptor) determinization and minimization, and then
> decodes the encoded labels back into their original values. This has
> the advantage that it is always defined and that it does not move output labels or costs along paths. It has the disadvantage that the
> result can be neither deterministic nor minimal.

> **Comments:**
> **username_1**: see also [On NFA reductions](http://www.csd.uwo.ca/faculty/ilie/TisF04.pdf) Ilie, Navarro, Yu  

---

