State complexity

It is an open problem whether all 2NFAs can be converted to 2DFAs with polynomially many states, i.e. whether there is a polynomial ${\displaystyle p(n)}$ such that for every ${\displaystyle n}$-state 2NFA there exists a ${\displaystyle p(n)}$-state 2DFA. The problem was raised by Sakoda and Sipser,[15] who compared it to the P vs. NP problem in the computational complexity theory. Berman and Lingas[16] discovered a formal relation between this problem and the L vs. NL open problem. This relation was further elaborated by Kapoutsis.[17]

If language ${\displaystyle L_{1}}$ requires m states and 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: between ${\displaystyle mn+m+n}$ and ${\displaystyle m+nm2^{0.79m}}$ states, see Jirásek, Jirásková and Šebej.[21]
• SVFA: ${\displaystyle mn}$ states, see Jirásek, Jirásková and Szabari.[22]
• 2DFA: between ${\displaystyle m+n}$ and ${\displaystyle 4m+n+4}$ states, see Kunc and Okhotin.[23]
• 2NFA: ${\displaystyle m+n}$ states, see Kunc and Okhotin.[24]

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.[21]
• SVFA: ${\displaystyle mn}$ states, see Jirásek, Jirásková and Szabari.[22]
• 2DFA: between ${\displaystyle m+n}$ and ${\displaystyle m+n+1}$ states, see Kunc and Okhotin.[23]
• 2NFA: between ${\displaystyle m+n}$ and ${\displaystyle m+n+1}$ states, see Kunc and Okhotin.[24]

If language L requires n states then how many states does its complement require?

• DFA: ${\displaystyle n}$ states, by exchanging accepting and rejecting states.
• NFA: ${\displaystyle 2^{n}}$ states, see Birget.[25]
• UFA: at least ${\displaystyle n^{{\tilde {\Omega }}(\log n)}}$ states, see Göös, Kiefer and Yuan,[26] and at most ${\displaystyle {\sqrt {n+1}}\cdot 2^{0.5n}}$ states, see Indzhev and Kiefer.[27]
• 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.[28]

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.[21]
• SVFA: ${\displaystyle \Theta (3^{n/3}2^{m})}$ states, see Jirásek, Jirásková and Szabari.[22]
• 2DFA: at least ${\displaystyle {\frac {2^{\Omega (n)}}{\log m}}}$ and at most ${\displaystyle 2m^{m+1}\cdot 2^{n^{n+1}}}$ states, see Jirásková and Okhotin.[29]

• 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.[21]
• SVFA: ${\displaystyle {\frac {3}{4}}2^{n}}$ states, see Jirásek, Jirásková and Szabari.[22]
• 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.[29]

• DFA: ${\displaystyle 2^{n}}$ states, see Mirkin,[30] Leiss,[31] 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.[22]
• 2DFA: between ${\displaystyle n+1}$ and ${\displaystyle n+2}$ states, see Jirásková and Okhotin.[29]

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.[32]
• 2DFA to DFA: ${\displaystyle g(n)+O(n)}$ states, see Chrobak[32] and Kunc and Okhotin.[33]
• 2NFA to DFA: ${\displaystyle O(g(n))}$ states, see Mereghetti and Pighizzini.[34] and Geffert, Mereghetti and Pighizzini.[35]
• NFA to 2DFA: at most ${\displaystyle O(n^{2})}$ states, see Chrobak.[32]
• 2NFA to 2DFA: at most ${\displaystyle n^{O(\log n)}}$ states, proved by implementing the method of Savitch's theorem, see Geffert, Mereghetti and Pighizzini.[35]
• UFA to DFA: ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$, see Okhotin.[36]
• NFA to UFA: ${\displaystyle g(n)+O(n^{2})}$, see Okhotin.[36]

• 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.[23]
• 2NFA: ${\displaystyle m+n}$ states, see Kunc and Okhotin.[24]

• 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.[23]
• 2NFA: between ${\displaystyle m+n}$ and ${\displaystyle m+n+1}$ states, see Kunc and Okhotin.[24]

• 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)^{\Theta (1)}}}$ states, see Raskin,[37] and at most ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$ states, see Okhotin.[36]
• 2DFA: at least ${\displaystyle n}$ and at most ${\displaystyle 2n+3}$ states, see Kunc and Okhotin.[23]
• 2NFA: at least ${\displaystyle n}$ and at most ${\displaystyle O(n^{8})}$ states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.[28]

• 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^{\Theta ({\sqrt {(m+n)\log(m+n)}})}}$ states, see Kunc and Okhotin.[23]
• 2NFA: ${\displaystyle e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}}$ states, see Kunc and Okhotin.[23]

• 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.[36]
• 2DFA: ${\displaystyle \Theta ((g(n))^{2})}$ states, see Kunc and Okhotin.[23]
• 2NFA: ${\displaystyle \Theta (g(n))}$ states, see Kunc and Okhotin.[23]