DFA -> regular expression

问题:

I've written a DFA on paper, and want to translate it into a set of regular expressions. Does anybody know a good tool to do this?

回答1:

From my little google search, I found JFLAP. They also have a tutorial on how to Convert FA to regular expression.

JFLAP

JFLAP is software for experimenting with formal languages topics including nondeterministic finite automata, nondeterministic pushdown automata, multi-tape Turing machines, several types of grammars, parsing, and L-systems. In addition to constructing and testing examples for these, JFLAP allows one to experiment with construction proofs from one form to another, such as converting an NFA to a DFA to a minimal state DFA to a regular expression or regular grammar. Click here for more information on what one can do with JFLAP.

回答2:

If what you want is a parser, there's no need to translate into regular expressions as an intermediate form. You can code a DFA fairly straightforwardly using flex or re2c. The coding for multiple states is not the common case, so it feels slightly unnatural at first (and it's not well covered in tutorials), but once you get rolling with it, it's really easy.