12
$\begingroup$

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), 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?

$\endgroup$
  • $\begingroup$ the video is apparently on the standard determinizing algorithm. see eg NFA minimization without determinization, stackoverflow $\endgroup$ – vzn Jul 16 '13 at 23:05
  • $\begingroup$ If you do the naive NFA->DFA conversion (using the product construction), how large is the resulting DFA? (before minimization) $\endgroup$ – D.W. Jul 17 '13 at 1:30
  • 2
    $\begingroup$ What do you you want to do with the DFA? If you are interested in inclusion checks, there are algorithms to do that directly. $\endgroup$ – Vijay D Jul 17 '13 at 2:33
  • $\begingroup$ 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. $\endgroup$ – Jendas Jul 17 '13 at 6:44
  • 1
    $\begingroup$ 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... $\endgroup$ – Aryeh Jul 17 '13 at 16:40
6
$\begingroup$

Have you tried Brzozowski's 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:

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jendas Jul 17 '13 at 6:59
  • 2
    $\begingroup$ I came, I asked, I divided, I conquered $\endgroup$ – Jendas Jul 18 '13 at 10:39
2
$\begingroup$

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 which can vary significantly in performance on average.

it is also known more informally as "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:

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

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.

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.

$\endgroup$
  • $\begingroup$ see also On NFA reductions Ilie, Navarro, Yu $\endgroup$ – vzn Jul 17 '13 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.