Minimally Equivalent DFA

A minimally equivalent DFA is a DFA that is equivalent to another DFA, while being minimal (having the least number of states & transitions). The process of converting a DFA to its minimal form is known as minimalisation.

A minimal DFA, $M^{\ast }$, for some language $L$ is one that recognises $L$ while having the least number of states. That is, if we were to remove a transition or state from $M^{\ast }$, it no longer recognises $L$.

Recall the definition of equivalence (in terms of finite state automata):

The minimally equivalent DFA is not unique.

Take a DFA $D$. We could have DFAs $M_1,M_2$ where $M_1\ne M_2$ both being minimally equivalent DFAs for $D$. Both $M_1$ and $M_2$ would have the same number of states, but apart from that, they can be totally different.

Procedure §

From an NFA §

This process requires both determinisation and reversal.

For a given NFA, $N$:

1. Reversal the NFA to obtain $N_{reverse}$

2. Determinise $N_{reverse}$ to produce $D$

3. Reverse $D$ to produce $N_{rev}$ (it could be that this is a DFA, but in most cases, reversal results in an NFA)

4. Determinise again (this is because reversing may add $ϵ$-transitions, which need to be removed in a DFA)

For a DFA §

#todo See https://people.csail.mit.edu/rrw/6.045-2020/lec5-before-class.pdf

Relation To Fooling Sets §

A DFA, $D$, for some language $L$, is minimal if there exists a fooling set for $L$ where its size, $|F|$ is exactly equal to the number of states of $D$. This is because the fooling set produces a lower bound for the number of states needed to recognise a language, hence being equal to the lower bound gives us the smallest, or minimal DFA.

Examples §

2: NFA to minimally equivalent DFA

Convert the NFA given below to its minimally equivalent DFA:

We start by reversing the NFA:

%%🖋 Edit in Excalidraw, and the dark exported image%%

Then, we determinise this new NFA:

%%🖋 Edit in Excalidraw, and the dark exported image%%

#todo later