HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Are DFAs unique?

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#67840, answer score: 12

Revisions (0)

No revisions yet.