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

Is the set of minimal DFA decidable?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dfathedecidableminimalset

Problem

Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for every other DFA $B$ with less states than $A$, $L(A)\ne L(B)$ holds. I'm trying to figure out how come that $\mathrm{MIN}_{\mathrm{DFA}} \in R$? How come it is decidable?

What is about this kind of DFAs that is easy to decide?

Solution

Given two DFAs $A,B$, it is decidable (even efficient!) whether $L(A) = L(B)$: use the product construction to get a DFA for $L(A) \triangle L(B)$, and now use reachability analysis.

In order to determine whether $A$ is a minimal DFA, one can just try all DFAs $B$ with less states, looking for one satisfying $L(A) = L(B)$. Alternatively, there are algorithms for minimizing DFAs which are vastly more efficient than that approach. They are even more efficient if all you want to know is whether the DFA is minimal or not.

Context

StackExchange Computer Science Q#3044, answer score: 9

Revisions (0)

No revisions yet.