How do I find out if a regex implementation uses DFA or NFA?

Question

I came across the question of whether a particular regex implementation is based on DFA or NFA.

What are the starting points for me to figure this out. One may also ask: what am I looking for? What are the main models and / or characteristics? A good and explanatory link or small comparisons (even if they are not directly related to the regular expression) are excellent.

Answer 1

I think you mean "regular expression", not an algorithm (in the usual sense).

You can test using well-known expressions that are known to cause problems with one or the other approach. We are also looking for functions that are easier to implement in one or the other (this is not a reliable approach - developers of regular expression engines are finding new ways to implement previously complex things).

Usually the answer is to read the documentation or look at a known link ( “Mastering Regular Expressions” documents many popular cases). Finally, why not ask the authors?

Answer 2

If it is a black box, then give it some input and measure its temporal characteristics with a pathological case with reference to the graphs in this NFS discussion vs regex reuse . (note that the NFS graph is microseconds, not seconds).

Also, if it is a pure NFA, then it will not have some of the irregular functions that are found, it is some "regular expression" parsers that require backtracking.

Alternatively, see the documentation for the RxParser class; The documentation does not appear to be available on the Internet and requires viewing the creak time.