NFA DFA and Regex to Transition Table [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking us to recommend or find a tool, library or favorite off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

Closed 8 years ago.

Improve this question

I have been looking out for some algorithm that has in input a regular expression or a string and that converts it into an NFA and then a DFA, and that would actually print out the transition table of the corresponding final DFA.

I'am thus wondering if there is already an algorithm or C or Python library that does that,or if you have suggestions of algorithms to use, that I could implement.

Thank you.

Answer 1

I'm not certain if either of these links might help you.

The first provide a very simple NFA/DFA implementation in Python, with conversion from NFA to DFA. It doesn't generate the NFA from a regex though, but it is not so difficult to do. The second site provides a long discussion on NFA vs DFA, including numerous code examples (mostly in C) and links to external libraries that I know little of. The third and fourth links provide the source code of two regex engines implementation developped by the second article's author, including parsing from regex to NFA, then conversion from NFA to DFA. Note however that I haven't had a look at either of these projects.

• https://gist.github.com/Arachnid/491973
• http://swtch.com/~rsc/regexp/
• https://code.google.com/p/re1/source/browse/
• https://code.google.com/p/re2/source/browse/

Otherwise, I would mention that most real world regex engines use NFA, not DFA, because of some extended features that simply can't be performed with a DFA. So if none of hte links above can help you, then you might have some luck looking at compiler-compilers, since they are the ones that actually use DFAs.