State complexity is an area oftheoretical computer sciencedealing with the size of abstract automata,such as different kinds offinite automata.The classical result in the area is thatsimulating an${\displaystyle n}$-statenondeterministic finite automatonby adeterministic finite automatonrequires exactly${\displaystyle 2^n}$ states in the worst case.

Finite automata can bedeterministic andnondeterministic,one-way (DFA, NFA)andtwo-way(2DFA, 2NFA).Other related classes areunambiguous (UFA),self-verifying (SVFA)andalternating (AFA) finite automata.These automata can also be two-way (2UFA, 2SVFA, 2AFA).

All these machines can accept exactly theregular languages.However, the size of different types of automatanecessary to accept the same language(measured in the number of their states)may be different.For any two types of finite automata,thestate complexity tradeoff between themis aninteger function${\displaystyle f}$where${\displaystyle f(n)}$ is the least number of states in automata of the second typesufficient to recognize every languagerecognized by an${\displaystyle n}$-state automaton of the first type.The following results are known.

• NFA to DFA:${\displaystyle 2^n}$ states. This is thesubset construction byRabin andScott,^[1] proved optimal byLupanov.^[2]

• UFA to DFA:${\displaystyle 2^n}$ states, seeLeung,^[3] An earlier lower bound by Schmidt^[4] was smaller.
• NFA to UFA:${\displaystyle 2^n-1}$ states, see Leung.^[3] There was an earlier smaller lower bound by Schmidt.^[4]
• SVFA to DFA:${\displaystyle \mathrm{\Theta }(3^{n/3})}$ states, see Jirásková andPighizzini^[5]
• 2DFA to DFA:${\displaystyle n(n^n-(n-1{)}^n)}$ states, seeKapoutsis.^[6] Earlier construction byShepherdson^[7] used more states, and an earlier lower bound by Moore^[8] was smaller.
• 2DFA to NFA:${\displaystyle (\genfrac{}{}{0ex}{}{2n}{n+1})=O(\frac{4^n}{\sqrt{n}})}$, see Kapoutsis.^[6] Earlier construction byBirget^[9] used more states.
• 2NFA to NFA:${\displaystyle (\genfrac{}{}{0ex}{}{2n}{n+1})}$, see Kapoutsis.^[6]
  • 2NFA to NFA accepting the complement:${\displaystyle O(4^n)}$ states, seeVardi.^[10]
• AFA to DFA:${\displaystyle 2^{2^n}}$ states, seeChandra,Kozen andStockmeyer.^[11]
• AFA to NFA:${\displaystyle 2^n}$ states, see Fellah, Jürgensen and Yu.^[12]
• 2AFA to DFA:${\displaystyle 2^{n{2}^n}}$, seeLadner,Lipton andStockmeyer.^[13]
• 2AFA to NFA:${\displaystyle 2^{\mathrm{\Theta }(n\log n)}}$, seeGeffert and Okhotin.^[14]

Unsolved problem in computer science

Does every${\displaystyle n}$-state 2NFA have an equivalent${\displaystyle \mathrm{poly}(n)}$-state 2DFA?

More unsolved problems in computer science

It is anopen problem whether all 2NFAs can be converted to 2DFAswith polynomially many states, i.e. whether there is a polynomial${\displaystyle p(n)}$such that for every${\displaystyle n}$-state 2NFAthere exists a${\displaystyle p(n)}$-state 2DFA.The problem was raised by Sakoda andSipser,^[15]who compared it to theP vs. NP problem in thecomputational complexity theory.Berman andLingas^[16] discovered a formal relation between this problemand theL vs.NL open problem.This relation was further elaborated byKapoutsis.^[17]

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${\displaystyle f(m,n)}$ such that

• for each m-state X-automaton A and n-state X-automaton B there is an${\displaystyle f(m,n)}$-state X-automaton for${\displaystyle L(A)\circ L(B)}$, and
• for all integers m, n there is an m-state X-automaton A and an n-state X-automaton B such that every X-automaton for${\displaystyle L(A)\circ L(B)}$ must have at least${\displaystyle f(m,n)}$ states.

Analogous definition applies for operations with any number of arguments.

The first results on state complexity of operations for DFAswere published by Maslov^[18]and by Yu, Zhuang andSalomaa.^[19]Holzer andKutrib^[20]pioneered the state complexity of operations on NFA.The known results for basic operations are listed below.

If language${\displaystyle L_1}$ requires m statesand language${\displaystyle L_2}$ requires n states,how many states does${\displaystyle L_1\cup L_2}$ require?

• DFA:${\displaystyle mn}$ states, see Maslov^[18] and Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle m+n+1}$ states, see Holzer and Kutrib.^[20]
• UFA: at least${\displaystyle min(n,m{)}^{\mathrm{\Omega }(\log (min(n,m)))}}$;^[21] between${\displaystyle mn+m+n}$ and${\displaystyle m+nm{2}^{0.79m}}$ states, see Jirásek, Jirásková and Šebej.^[22]
• SVFA:${\displaystyle mn}$ states, see Jirásek, Jirásková and Szabari.^[23]
• 2DFA: between${\displaystyle m+n}$ and${\displaystyle 4m+n+4}$ states, see Kunc and Okhotin.^[24]
• 2NFA:${\displaystyle m+n}$ states, see Kunc and Okhotin.^[25]

How many states does${\displaystyle L_1\cap L_2}$ require?

• DFA:${\displaystyle mn}$ states, see Maslov^[18] and Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle mn}$ states, see Holzer and Kutrib.^[20]
• UFA:${\displaystyle mn}$ states, see Jirásek, Jirásková and Šebej.^[22]
• SVFA:${\displaystyle mn}$ states, see Jirásek, Jirásková and Szabari.^[23]
• 2DFA: between${\displaystyle m+n}$ and${\displaystyle m+n+1}$ states, see Kunc and Okhotin.^[24]
• 2NFA: between${\displaystyle m+n}$ and${\displaystyle m+n+1}$ states, see Kunc and Okhotin.^[25]

If language L requires n statesthen how many states does itscomplement require?

• DFA:${\displaystyle n}$ states, by exchanging accepting and rejecting states.
• NFA:${\displaystyle 2^n}$ states, see Birget.^[26] or Jirásková^[27]
• UFA: at least${\displaystyle n^{\tilde{\mathrm{\Omega }}(\log n)}}$ states, see Göös, Kiefer and Yuan,^[21] (this follows an earlier bound by Raskin^[28]); and at most${\displaystyle \sqrt{n+1}\cdot 2^{0.5n}}$ states, see Indzhev and Kiefer.^[29]
• SVFA:${\displaystyle n}$ states, by exchanging accepting and rejecting states.
• 2DFA: at least${\displaystyle n}$ and at most${\displaystyle 4n}$ states, see Geffert, Mereghetti and Pighizzini.^[30]

How many states does${\displaystyle L_1{L}_2=\{w_1{w}_2\mid w_1\in L_1,w_2\in L_2\}}$ require?

• DFA:${\displaystyle m\cdot 2^n-2^{n-1}}$ states, see Maslov^[18] and Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle m+n}$ states, see Holzer and Kutrib.^[20]
• UFA:${\displaystyle \frac{3}{4}{2}^{m+n}-1}$ states, see Jirásek, Jirásková and Šebej.^[22]
• SVFA:${\displaystyle \mathrm{\Theta }(3^{n/3}{2}^m)}$ states, see Jirásek, Jirásková and Szabari.^[23]
• 2DFA:at least${\displaystyle \frac{2^{\mathrm{\Omega }(n)}}{\log m}}$ and at most${\displaystyle 2m^{m+1}\cdot 2^{n^{n+1}}}$ states, see Jirásková and Okhotin.^[31]

• DFA:${\displaystyle \frac{3}{4}{2}^n}$ states, see Maslov^[18] and Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle n+1}$ states, see Holzer and Kutrib.^[20]
• UFA:${\displaystyle \frac{3}{4}{2}^n}$ states, see Jirásek, Jirásková and Šebej.^[22]
• SVFA:${\displaystyle \frac{3}{4}{2}^n}$ states, see Jirásek, Jirásková and Szabari.^[23]
• 2DFA:at least${\displaystyle \frac{1}{n}{2}^{\frac{n}{2}-1}}$ and at most${\displaystyle 2^{O(n^{n+1})}}$ states, see Jirásková and Okhotin.^[31]

• DFA:${\displaystyle 2^n}$ states, see Mirkin,^[32] Leiss,^[33] and Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle n+1}$ states, see Holzer and Kutrib.^[20]
• UFA:${\displaystyle n}$ states.
• SVFA:${\displaystyle 2n+1}$ states, see Jirásek, Jirásková and Szabari.^[23]
• 2DFA:between${\displaystyle n+1}$ and${\displaystyle n+2}$ states, see Jirásková and Okhotin.^[31]

State complexity of finite automata with a one-letter (unary) alphabet, pioneered byChrobak,^[34] is different from the multi-letter case.

Let${\displaystyle g(n)=e^{\mathrm{\Theta }(\sqrt{n\ln n})}}$ beLandau's function.

For a one-letter alphabet, transformations between different types of finite automata are sometimes more efficient than in the general case.

• NFA to DFA:${\displaystyle g(n)+O(n^2)}$ states, see Chrobak.^[34]
• 2DFA to DFA:${\displaystyle g(n)+O(n)}$ states, see Chrobak^[34] and Kunc and Okhotin.^[35]
• 2NFA to DFA:${\displaystyle O(g(n))}$ states, see Mereghetti andPighizzini.^[36] andGeffert, Mereghetti and Pighizzini.^[37]
• NFA to 2DFA: at most${\displaystyle O(n^2)}$ states, see Chrobak.^[34]
• 2NFA to 2DFA: at most${\displaystyle n^{O(\log n)}}$ states, proved by implementing the method ofSavitch's theorem, see Geffert, Mereghetti and Pighizzini.^[37]
• UFA to DFA:${\displaystyle e^{\mathrm{\Theta }(\sqrt[3]{n(\ln n{)}^2})}}$, see Okhotin.^[38]
• NFA to UFA:${\displaystyle g(n)+O(n^2)}$, see Okhotin.^[38]

• DFA:${\displaystyle mn}$ states, see Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle m+n+1}$ states, see Holzer and Kutrib.^[20]
• 2DFA: between${\displaystyle m+n}$ and${\displaystyle 2m+n+4}$ states, see Kunc and Okhotin.^[24]
• 2NFA:${\displaystyle m+n}$ states, see Kunc and Okhotin.^[25]

• DFA:${\displaystyle mn}$ states, see Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle mn}$ states, see Holzer and Kutrib.^[20]
• 2DFA: between${\displaystyle m+n}$ and${\displaystyle m+n+1}$ states, see Kunc and Okhotin.^[24]
• 2NFA: between${\displaystyle m+n}$ and${\displaystyle m+n+1}$ states, see Kunc and Okhotin.^[25]

• DFA:${\displaystyle n}$ states.
• NFA:${\displaystyle g(n)+O(n^2)}$ states, see Holzer and Kutrib.^[20]
• UFA: at least${\displaystyle n^{(\log \log \log n{)}^{\mathrm{\Theta }(1)}}}$ states, see Raskin,^[39] and at most${\displaystyle e^{\mathrm{\Theta }(\sqrt[3]{n(\ln n{)}^2})}}$ states, see Okhotin.^[38]
• 2DFA: at least${\displaystyle n}$ and at most${\displaystyle 2n+3}$ states, see Kunc and Okhotin.^[24]
• 2NFA: at least${\displaystyle n}$ and at most${\displaystyle O(n^8)}$ states. The upper bound is by implementing the method of theImmerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.^[30]

• DFA:${\displaystyle mn}$ states, see Yu, Zhuang and Salomaa.^[19]
• NFA: between${\displaystyle m+n-1}$ and${\displaystyle m+n}$ states, see Holzer and Kutrib.^[20]
• 2DFA:${\displaystyle e^{\mathrm{\Theta }(\sqrt{(m+n)\log (m+n)})}}$ states, see Kunc and Okhotin.^[24]
• 2NFA:${\displaystyle e^{\mathrm{\Theta }(\sqrt{(m+n)\log (m+n)})}}$ states, see Kunc and Okhotin.^[24]

• DFA:${\displaystyle (n-1{)}^2+1}$ states, see Yu, Zhuang and Salomaa.^[19]
• NFA:${\displaystyle n+1}$ states, see Holzer and Kutrib.^[20]
• UFA:${\displaystyle (n-1{)}^2+1}$ states, see Okhotin.^[38]
• 2DFA:${\displaystyle \mathrm{\Theta }((g(n){)}^2)}$ states, see Kunc and Okhotin.^[24]
• 2NFA:${\displaystyle \mathrm{\Theta }(g(n))}$ states, see Kunc and Okhotin.^[24]

Surveys of state complexitywere written by Holzer and Kutrib^[40][41]and by Gao et al.^[42]

New research on state complexityis commonly presented at the annual workshops onDescriptional Complexity of Formal Systems (DCFS),at theConference on Implementation and Application of Automata (CIAA),and at various conferences ontheoretical computer science in general.

• Finite-state machines

• CS1: long volume value