NFA minimization

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 NP-hard. No efficient (polynomial time) algorithms are known. Nonetheless, algorithms exist which implement useful functionality such as Kameda-Weiner.[1] Additional research has been published on the topic.

State minimal NFA

Unlike deterministic finite automata (DFA), minimal NFAs may not be unique. There may be multiple NFAs of the same size which accept the same input sequences (recognize the same regular language), but for which there are no NFAs with fewer states which also recognize the same input sequences.

gollark: In what language?
gollark: Maybe you could make some sort of fancy tool to automatically try and flatten stuff into fewer dimensions. Although this *may* be somewhat impossible.
gollark: So it's stored as... a mapping from dimension to position instead?
gollark: What do you mean "vector list storage"? Does it run-length-encode dimensions a bit or just use resizæble arrays for position?
gollark: I guess I can just tweak the PotatOS Privacy Policy to allow it, yes.

References
  1. Kameda, Tsunehiko "Tiko"; Weiner, Peter (August 1970). "On the State Minimization of Nondeterministic Finite Automata". IEEE Transactions on Computers. IEEE. 100 (7): 617–627. doi:10.1109/T-C.1970.222994. Retrieved 2020-05-03.
  • A modified C# implementation of Kameda-Weiner (1970)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.