search

jackwadden / VASim

VASim is a virtual homogeneous non-deterministic finite automata automata simulator and transformation tool. VASim can parse, transform, simulate, and profile homogeneous NFAs, and is meant to be an open tool for automata processing research. VASim can also be extended to support hypothetical automata processing elements.
BSD 3-Clause "New" or "Revised" License
34 stars 20 forks source link

Convert to DFA #31

Closed karakchi closed 5 years ago

karakchi commented 6 years ago

Hello Jack,

I am trying to use -D option to convert anml to DFA but it takes too long time, is that normal? I started with Levenshtein which is about 2000 stes but it is running for long time now and did not finish.

Any suggestions?

Rasha

jackwadden commented 6 years ago

DFA construction is worst-case exponentially expensive in both time and space. The true cost has more to do with the number of possible configurations that the NFA could be in at any one time. We need a DFA state for each possible configuration of the NFA. Levenshtein is a particularly nasty example where there are many, many, many, many configurations in practice, so I bet the cost is closer to exponential than say.... a typical Snort NIDS rule that's already almost a DFA.

Also beware that DFA construction can consume massive amounts of memory. Once you're out of RAM and start thrashing, DFA construction will most likely take too long to be practically useful. Even if you have infinite RAM, you still have to pay exponential time, which might also take too long to be practically useful.

Hope this helps.