Algorithm for converting very large NFA to DFA 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?
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:


On the performance of automata minimization algorithms, 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.