automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

(a branch of

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

), NFA minimization is the task of transforming a given

nondeterministic finite automaton In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is ''uniquely'' determined by its source state and input symbol, and * reading an input symbol is required for each state tr ...

(NFA) into an equivalent NFA that has a minimum number of states, transitions, or both. While efficient algorithms exist for

DFA minimization 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 equival ...

, NFA minimization is

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...

. No efficient (polynomial time) algorithms are known, and under the standard assumption P ≠

PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

, none exist. The most efficient known algorithm is the Kameda‒Weiner algorithm.

Non-uniqueness of minimal NFA

Unlike

deterministic finite automata In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...

, minimal NFAs may not be unique. There may be multiple NFAs of the same size which accept the same

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

, but for which there is no equivalent NFA or DFA with fewer states.

References

{{Reflist, refs= {{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 ''IEEE Transactions on Computers'' is a monthly peer-reviewed scientific journal covering all aspects of computer design. It was established in 1952 and is published by the IEEE Computer Society. The editor-in-chief is Ahmed Louri, David and Marily ...

, volume=C-19 , issue=7 , publisher=

IEEE The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...

, doi=10.1109/T-C.1970.222994 , pages=617–627 , s2cid=31188224 , url=https://www.researchgate.net/publication/3045459 , access-date=2020-05-03 {{citation , last1 = Jiang , first1 = Tao , last2 = Ravikumar , first2 = B. , title = Minimal NFA Problems are Hard , journal = SIAM Journal on Computing , volume = 22 , number = 6 , pages = 1117–1141 , year = 1993 , doi=10.1137/0222067 , url = https://doi.org/10.1137/0222067 , url-access = subscription

External links

* A modified C# implementation of Kameda-Weiner (1970

PSPACE-complete problems Finite automata