1
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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". $\endgroup$ – Shaull Jun 11 '13 at 9:05
  • 2
    $\begingroup$ 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. $\endgroup$ – babou Jun 11 '13 at 9:38
  • $\begingroup$ 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? $\endgroup$ – Jendas Jun 11 '13 at 9:58
  • $\begingroup$ 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. $\endgroup$ – babou Jun 11 '13 at 10:28
  • 1
    $\begingroup$ computing the minimal NFA for a DFA, its Pspace complete. $\endgroup$ – vzn Jun 11 '13 at 23:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Juho Jun 11 '13 at 16:57
  • 2
    $\begingroup$ No need to google: we have a reference question right here. $\endgroup$ – Raphael Jun 11 '13 at 17:00
  • 1
    $\begingroup$ I did not say google :-) ... I try to be agnostic $\endgroup$ – babou Jun 11 '13 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.