patternModerate
Are DFAs unique?
Viewed 0 times
areuniquedfas
Problem
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#67840, answer score: 12
Revisions (0)
No revisions yet.