DFA minimization

en · unofficial · sha256:61eb938f2a8483f3bc6115cc8a1121754b774bef0cccd23e093dadc34fc95073

There are three classes of states that can be removed or merged from the original DFA without affecting the language it accepts. * ''Unreachable states'' are the states that are not reachable from the initial state of the DFA, for any input string. These states can be removed. * ''Dead states'' are the states from which no final state is reachable. These states can be removed unless the automaton is required to be [[Deterministic finite automaton#Complete and incomplete|complete]]. * ''Nondistinguishable states'' are those that cannot be distinguished from one another for any input string. These states can be merged.

Referencing norms: DeadRemovableWithCaveat, DeadState, Distinguishable, Nondistinguishable, NondistinguishableMergeable, UnreachableRemovable

en · unofficial · sha256:a126348d601a384cb278ccb62d784745ffc2a688cd43d691885f221079fb207a

For each regular language, there exists a minimal deterministic automaton that accepts it, that is, a DFA with a minimum number of states. By the [[Myhill-Nerode theorem]], this DFA is unique (except that states can be given different names).<ref>{{harvtxt|Hopcroft|Ullman|1979}}, Section 3.4, Theorem 3.10, p.67</ref><ref>{{harvtxt|Hopcroft|Motwani|Ullman|2001}}, Section 4.4.3, "Minimization of DFA's", p. 159, and p. 164 (remark after Theorem 4.26)</ref> The minimal DFA ensures minimal computational cost for tasks such as [[pattern matching]].

Referencing norms: MinimalDfaExists, MinimalDfaUnique, TwoMinimalAutomataIsomorphic, UniquenessProofStaysInSource

en · unofficial · sha256:6b5f8fc0d0490ea9209aeba36ae938722b6f27e84e89ae2490461c84a5154994

While the above procedures work for DFAs, the method of partitioning does not work for [[non-deterministic finite automaton|non-deterministic finite automata]] (NFAs).<ref>{{harvtxt|Hopcroft|Motwani|Ullman|2001}}, Section 4.4, Figure labeled "Minimizing the States of an NFA", p. 163.</ref> While an exhaustive search may minimize an NFA, there is no [[polynomial-time algorithm]] to minimize general NFAs unless {{nowrap|[[P (complexity)|P]] {{=}} [[PSPACE]]}}, an unsolved [[conjecture]] in [[computational complexity theory]] that is widely believed to be false. However, there are methods of [[NFA minimization]] that may be more efficient than brute force search.{{sfnp|Kameda|Weiner|1970}}

Referencing norms: NfaMinimizationOutOfScope

en · unofficial · sha256:c7126b6640c8b331517234d446434b443a80e315244680150b60c18ec90d0fcf

In [[automata theory]] (a branch of [[theoretical computer science]]), '''DFA minimization''' is the task of transforming a given [[deterministic finite automaton]] (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same [[regular language]]. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.<ref>{{harvtxt|Hopcroft|Motwani|Ullman|2001}}, Section 4.4.3, "Minimization of DFA's".</ref>

Referencing norms: MinimizationTask

en · unofficial · sha256:5bd0ee7810dd69364c7f3ba78fd7dbb436bb80c5894adb9dd0e6d63768aacce9

The state <math>p</math> of a deterministic finite automaton <math>M=(Q,\Sigma,\delta,q_0,F)</math> is unreachable if no string <math>w</math> in <math>\Sigma^*</math> exists for which <math>p=\delta^*(q_0,w)</math>. In this definition, <math>Q</math> is the set of states, <math>\Sigma</math> is the set of input symbols, <math>\delta</math> is the transition function (mapping a state and an input symbol to a set of states), <math>\delta^*</math> is its extension to strings (also known as extended transition function), <math>q_0</math> is the initial state, and <math>F</math> is the set of accepting (also known as final) states. Reachable states can be obtained with the following algorithm:

Referencing norms: UnreachableState