Transformation between variants of finite automata
Finite automata can be deterministic and nondeterministic, one-way (DFA, NFA) andThe 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 such that for every -state 2NFA there exists a -state 2DFA. The problem was raised by Sakoda and Sipser, who compared it to the P vs. NP problem in theState complexity of operations for finite automata
Given a binary regularity-preserving operation on languages and a family of automata X (DFA, NFA, etc.), the state complexity of is an integer function such that * for each m-state X-automaton A and n-state X-automaton B there is an -state X-automaton for , 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 must have at least states. Analogous definition applies for operations with any number of arguments. The first results on state complexity of operations for DFAs were published by Maslov and by Yu, Zhuang and Salomaa. Holzer and Kutrib pioneered the state complexity of operations on NFA. The known results for basic operations are listed below.Union
If language requires m states and language requires n states, how many states does require? * DFA: states, see Maslov and Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * UFA: between and states, see Jirásek, Jirásková and Šebej. * SVFA: states, see Jirásek, Jirásková and Szabari. * 2DFA: between and states, see Kunc and Okhotin. * 2NFA: states, see Kunc and Okhotin.Intersection
How many states does require? * DFA: states, see Maslov and Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * UFA: states, see Jirásek, Jirásková and Šebej. * SVFA: states, see Jirásek, Jirásková and Szabari. * 2DFA: between and states, see Kunc and Okhotin. * 2NFA: between and states, see Kunc and Okhotin.Complementation
If language L requires n states then how many states does its ''complement'' require? * DFA: states, by exchanging accepting and rejecting states. * NFA: states, see Birget. * UFA: at least states, see Göös, Kiefer and Yuan, and at most states, see Indzhev and Kiefer. * SVFA: states, by exchanging accepting and rejecting states. * 2DFA: at least and at most states, see Geffert, Mereghetti and Pighizzini.Concatenation
How many states does require? * DFA: states, see Maslov and Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * UFA: states, see Jirásek, Jirásková and Šebej. * SVFA: states, see Jirásek, Jirásková and Szabari. * 2DFA: at least and at most states, see Jirásková and Okhotin.Kleene star
* DFA: states, see Maslov and Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * UFA: states, see Jirásek, Jirásková and Šebej. * SVFA: states, see Jirásek, Jirásková and Szabari. * 2DFA: at least and at most states, see Jirásková and Okhotin.Reversal
* DFA: states, see Mirkin, Leiss, and Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * UFA: states. * SVFA: states, see Jirásek, Jirásková and Szabari. * 2DFA: between and states, see Jirásková and Okhotin.Finite automata over a unary alphabet
State complexity of finite automata with a one-letter (''unary'') alphabet, pioneered by Chrobak, is different from the multi-letter case. Let be Landau's function.Transformation between models
For a one-letter alphabet, transformations between different types of finite automata are sometimes more efficient than in the general case. * NFA to DFA: states, see Chrobak. * 2DFA to DFA: states, see Chrobak and Kunc and Okhotin. * 2NFA to DFA: states, see Mereghetti and Pighizzini. and Geffert, Mereghetti and Pighizzini. * NFA to 2DFA: at most states, see Chrobak. * 2NFA to 2DFA: at most states, proved by implementing the method of Savitch's theorem, see Geffert, Mereghetti and Pighizzini. * UFA to DFA: , see Okhotin. * NFA to UFA: , see Okhotin.Union
* DFA: states, see Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * 2DFA: between and states, see Kunc and Okhotin. * 2NFA: states, see Kunc and Okhotin.Intersection
* DFA: states, see Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * 2DFA: between and states, see Kunc and Okhotin. * 2NFA: between and states, see Kunc and Okhotin.Complementation
* DFA: states. * NFA: states, see Holzer and Kutrib. * UFA: at least states, see Raskin, and at most states, see Okhotin. * 2DFA: at least and at most states, see Kunc and Okhotin. * 2NFA: at least and at most states. The upper bound is by implementing the method of the Immerman–Szelepcsényi theorem, see Geffert, Mereghetti and Pighizzini.Concatenation
* DFA: states, see Yu, Zhuang and Salomaa. * NFA: between and states, see Holzer and Kutrib. * 2DFA: states, see Kunc and Okhotin. * 2NFA: states, see Kunc and Okhotin.Kleene star
* DFA: states, see Yu, Zhuang and Salomaa. * NFA: states, see Holzer and Kutrib. * UFA: states, see Okhotin. * 2DFA: states, see Kunc and Okhotin. * 2NFA: states, see Kunc and Okhotin.Further reading
Surveys of state complexity were written by Holzer and Kutrib and by Gao et al. New research on state complexity is commonly presented at the annual workshops on Descriptional Complexity of Formal Systems (DCFS), at the Conference on Implementation and Application of Automata (CIAA), and at various conferences onReferences
{{reflist Finite automata