NFA minimization

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In automata theory (a branch of theoretical computer science), NFA minimization is the task of transforming a given nondeterministic finite automaton (NFA) into an equivalent NFA that has a minimum number of states. While efficient algorithms exist for DFA minimization, NFA minimization is PSPACE-complete. No efficient (polynomial time) algorithms are known, and under the standard assumption that P ≠ PSPACE, none exist. The most efficient known algorithm is the Kameda–Weiner algorithm.

In automata theory (a branch of theoretical computer science), NFA minimization is the task of transforming a given nondeterministic finite automaton (NFA) into an equivalent NFA that has a minimum number of states. While efficient algorithms exist for DFA minimization, NFA minimization is PSPACE-complete. No efficient (polynomial time) algorithms are known, and under the standard assumption that P ≠ PSPACE, none exist. The most efficient known algorithm is the Kameda–Weiner algorithm. For example, the language ending in ab , denoted by (a+b)^*ab over the alphabet \Sigma = \{a, b\} , has no NFA with fewer than 3 states. There is a three-state minimal DFA that deterministically tracks how much of the suffix ab has been seen so far (see picture NFA 1). Furthermore, there is a non-isomorphic minimal NFA for the same language that instead non-deterministically guesses at each a whether it begins the final ab , accepting if that guess is confirmed by the string's end (NFA 2).

External links

A modified C# implementation of Kameda–Weiner (1970)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1363153378 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.