2
$\begingroup$

For a given regular is expression, once we construct a deterministic finite automaton: is that automaton unique for that expression? In a sense, that no other DFA (different number of vertices or transitions) can be constructed from that same regular expression.

$\endgroup$
7
$\begingroup$

For every regular language there are infinitely many DFAs accepting the language. You can always add dummy states not reachable from the initial state, for example.

However, there is a unique DFA which has the minimum number of states, called the minimal automaton (or some such name). This is part of Myhill–Nerode theory.

$\endgroup$
  • $\begingroup$ (Unique up to isomorphism.) $\endgroup$ – reinierpost Feb 3 '17 at 9:50
  • $\begingroup$ How to make a state which is unreachable? Can a DFA be disconnected? $\endgroup$ – Gyanshu Apr 24 '17 at 16:14
  • 1
    $\begingroup$ @Gyanshu There is absolutely no requirement in the definition of DFA that its graph be connected. $\endgroup$ – Yuval Filmus Apr 24 '17 at 16:58

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.