State complexity is an area of theoretical computer science dealing with the size of abstract automata, such as different kinds of finite automata. The classical result in the area is that simulating an n {\displaystyle n} -state nondeterministic finite automaton by a deterministic finite automaton requires exactly 2 n {\displaystyle 2^{n}} states in the worst case.
Transformation between variants of finite automata Finite automata can be deterministic and nondeterministic, one-way (DFA, NFA) and two-way (2DFA, 2NFA). Other related classes are unambiguous (UFA), self-verifying (SVFA) and alternating (AFA) finite automata. These automata can also be two-way (2UFA, 2SVFA, 2AFA). All these machines can accept exactly the regular languages. However, the size of different types of automata necessary to accept the same language (measured in the number of their states) may be different. For any two types of finite automata, the state complexity tradeoff between them is an integer function f {\displaystyle f}
where f ( n ) {\displaystyle f(n)} is the least number of states in automata of the second type sufficient to recognize every language recognized by an n {\displaystyle n} -state automaton of the first type. The following results are known.
NFA to DFA: 2 n {\displaystyle 2^{n}} states. This is the subset construction by Rabin and Scott, proved optimal by Lupanov. UFA to DFA: 2 n {\displaystyle 2^{n}} states, see Leung, An earlier lower bound by Schmidt was smaller. NFA to UFA: 2 n − 1 {\displaystyle 2^{n}-1} states, see Leung. There was an earlier smaller lower bound by Schmidt. SVFA to DFA: Θ ( 3 n / 3 ) {\displaystyle \Theta (3^{n/3})} states, see Jirásková and Pighizzini 2DFA to DFA: n ( n n − ( n − 1 ) n ) {\displaystyle n(n^{n}-(n-1)^{n})} states, see Kapoutsis. Earlier construction by Shepherdson used more states, and an earlier lower bound by Moore was smaller. 2DFA to NFA: ( 2 n n + 1 ) = O ( 4 n n ) {\displaystyle {\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})} , see Kapoutsis. Earlier construction by Birget used more states. 2NFA to NFA: ( 2 n n + 1 ) {\displaystyle {\binom {2n}{n+1}}} , see Kapoutsis. 2NFA to NFA accepting the complement: O ( 4 n ) {\displaystyle O(4^{n})} states, see Vardi. AFA to DFA: 2 2 n {\displaystyle 2^{2^{n}}} states, see Chandra, Kozen and Stockmeyer. AFA to NFA: 2 n {\displaystyle 2^{n}} states, see Fellah, Jürgensen and Yu. 2AFA to DFA: 2 n 2 n {\displaystyle 2^{n2^{n}}} , see Ladner, Lipton and Stockmeyer. 2AFA to NFA: 2 Θ ( n log n ) {\displaystyle 2^{\Theta (n\log n)}} , see Geffert and Okhotin.
The 2DFA vs. 2NFA problem and logarithmic space
It is an open problem whether all 2NFAs can be converted to 2DFAs with polynomially many states, i.e. whether there is a polynomial p ( n ) {\displaystyle p(n)}
such that for every n {\displaystyle n} -state 2NFA there exists a p ( n ) {\displaystyle p(n)} -state 2DFA. The problem was raised by Sakoda and Sipser, who compared it to the P vs. NP problem in the computational complexity theory. Berman and Lingas discovered a formal relation between this problem and the L vs. NL open problem. This relation was further elaborated by Kapoutsis.
State complexity of operations for finite automata Given a binary regularity-preserving operation on languages ∘ {\displaystyle \circ }
and a family of automata X (DFA, NFA, etc.), the state complexity of ∘ {\displaystyle \circ }
is an integer function f ( m , n ) {\displaystyle f(m,n)} such that
… excerpt ends here. Continue reading the full article.
