3
$\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$

1 Answer 1

12
$\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$
3
  • 1
    $\begingroup$ (Unique up to isomorphism.) $\endgroup$ Feb 3, 2017 at 9:50
  • $\begingroup$ How to make a state which is unreachable? Can a DFA be disconnected? $\endgroup$
    – Gyanshu
    Apr 24, 2017 at 16:14
  • 3
    $\begingroup$ @Gyanshu There is absolutely no requirement in the definition of DFA that its graph be connected. $\endgroup$ Apr 24, 2017 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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