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$
7
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 10:28
  • 1
    $\begingroup$ computing the minimal NFA for a DFA, its Pspace complete. $\endgroup$
    – vzn
    Jun 11, 2013 at 23:39

1 Answer 1

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.

$\endgroup$
3
  • $\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, 2013 at 16:57
  • 2
    $\begingroup$ No need to google: we have a reference question right here. $\endgroup$
    – Raphael
    Jun 11, 2013 at 17:00
  • 1
    $\begingroup$ I did not say google :-) ... I try to be agnostic $\endgroup$
    – babou
    Jun 11, 2013 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.