NFA minimization: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:43, 24 December 2020

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, transitions, or both. While efficient algorithms exist for DFA minimization, NFA minimization is PSPACE-complete.^[1] No efficient (polynomial time) algorithms are known, and under the standard assumption P ≠ PSPACE, none exist. The most efficient known algorithm is the Kameda‒Weiner algorithm.^[2]

Non-uniqueness of minimal NFA

Unlike deterministic finite automata, minimal NFAs may not be unique. There may be multiple NFAs of the same size which accept the same regular language, but for which there is no equivalent NFA or DFA with fewer states.

References

^ Jiang, Tao; Ravikumar, B. (1993), "Minimal NFA Problems are Hard", SIAM Journal on Computing, 22 (issue): 1117–1141, doi:10.1137/0222067 {{citation}}: |number= has extra text (help)
^ Kameda, Tsunehiko; Weiner, Peter (August 1970). "On the State Minimization of Nondeterministic Finite Automata". IEEE Transactions on Computers. C-19 (7). IEEE: 617–627. doi:10.1109/T-C.1970.222994. Retrieved 2020-05-03.

External links

A modified C# implementation of Kameda-Weiner (1970) [1]

[TaoRavikumar93-1] Jiang, Tao; Ravikumar, B. (1993), "Minimal NFA Problems are Hard", SIAM Journal on Computing, 22 (issue): 1117–1141, doi:10.1137/0222067 {{citation}}: |number= has extra text (help)

[Kameda-Weiner_1970-2] Kameda, Tsunehiko; Weiner, Peter (August 1970). "On the State Minimization of Nondeterministic Finite Automata". IEEE Transactions on Computers. C-19 (7). IEEE: 617–627. doi:10.1109/T-C.1970.222994. Retrieved 2020-05-03.

[1]

[2]

@@ Line 7: / Line 7: @@
 == References ==
 {{Reflist|refs=
-<ref name="Kameda-Weiner_1970">{{cite journal |title=On the State Minimization of Nondeterministic Finite Automata |author-first1=Tsunehiko "Tiko" |author-last1=Kameda |author-first2=Peter |author-last2=Weiner |date=August 1970 |journal=[[IEEE Transactions on Computers]] |volume=100 |issue=7 |publisher=[[IEEE]] |doi=10.1109/T-C.1970.222994 |pages=617–627 |url=https://www.researchgate.net/publication/3045459_On_the_State_Minimization_of_Nondeterministic_Finite_Automata |access-date=2020-05-03}}</ref>
+<ref name="Kameda-Weiner_1970">{{cite journal |title=On the State Minimization of Nondeterministic Finite Automata |author-first1=Tsunehiko |author-last1=Kameda |author-first2=Peter |author-last2=Weiner |date=August 1970 |journal=[[IEEE Transactions on Computers]] |volume=C-19 |issue=7 |publisher=[[IEEE]] |doi=10.1109/T-C.1970.222994 |pages=617–627 |url=https://www.researchgate.net/publication/3045459_On_the_State_Minimization_of_Nondeterministic_Finite_Automata |access-date=2020-05-03}}</ref>
 <ref name="TaoRavikumar93">{{cite