Can we minimise regular expressions using known DFA minimisation algorithms?

Of course, converting NFA to DFA is not a problem. But what about the other direction?

My motivation is the notion of minimization regular expressions using the DFA minimization algorithm.

• Are you sure you have the directions right? What you ask is trivial. A DFA is in particular an NFA. The converse, however, requires the determinization process called the "subset-construction". – Shaull Jun 11 '13 at 9:05
• The answers to your question are in wikipedia. You should do a tiny bit of research before asking. The people who answer have only 24 hours each day. – babou Jun 11 '13 at 9:38
• True, but that was not what I meant. DFA is also an NFA. But can be from DFA somehow restored the original regular expression? Or at least some good guess can be provided? – Jendas Jun 11 '13 at 9:58
• Many regular expressions (or many FA) can define the same regular language and be transformed into each-other. So there is no knowing which you started from. What remains unique, if I may say, is the language defined. Now the minimal DFA is also unique (up to notations) for a given language, as it can be directly characterized from properties of the language - see Myhill-Nerode theorem. – babou Jun 11 '13 at 10:28
• computing the minimal NFA for a DFA, its Pspace complete. – vzn Jun 11 '13 at 23:39

You should have asked first what you wanted : your second line. Why assume that you have to reverse the determinization procedure to get back to a regular expression. You confused your readers. You might add it as a possible way you imagined to go about it, after you stated what you want, not before.

To find out how to get a RE from a FA, just search the web for : "convert finite automata to regular expressions". It is an interesting topic.

If you want a "minimal regular expression", just search for that. But I am not sure what minimal would mean (number of operators used ?).

If you want to find a "minimal NFA" search for that, but I gather it is a rather difficult problem, still under research.

If you want a "minimal DFA", search for that. It is a well explored problem.

• As noted, NFA minimization is not so well defined. There's work that shows SAT solvers are quite good at it though. Nowadays we can also minimize DFAs in $O(m \log n)$ time, assuming the usual $n \leq 2m$. – Juho Jun 11 '13 at 16:57
• No need to google: we have a reference question right here. – Raphael Jun 11 '13 at 17:00
• I did not say google :-) ... I try to be agnostic – babou Jun 11 '13 at 21:08