State minimisation
An important field where finite automata are being used is in hardware design, some components of hardware (chips) are based on simulating DFAs.
- Given a task, an NFA is designed, since it is easier to design than a DFA.
- This NFA is turned into a DFA doing the same thing (using subset construction). The number of states of the resulting DFA may increase significantly. The worst case scenario is .
- The resulting DFA is ‘minimised’, to obtain a DFA that has the minimum possible number of states for the given task.
title: There are various ways to do this, see recommended literature. - Finally, obtained DFA is hard-wired.