Content deleted Content added
m →Transformation between variants of finite automata: Misprints corrected |
m Moving Category:Finite automata to Category:Finite-state machines per Wikipedia:Categories for discussion/Speedy |
||
| (47 intermediate revisions by 19 users not shown) | |||
Line 7:
by a [[Deterministic finite automaton|deterministic]] finite automaton
requires exactly <math>2^n</math> states in the worst case.
==Transformation between variants of finite automata==
Line 23 ⟶ 22:
These automata can also be two-way (2UFA, 2SVFA, 2AFA).
All these machines can accept exactly the [[
However, the size of different types of automata
necessary to accept the same language
Line 36 ⟶ 35:
The following results are known.
* NFA to DFA: <math>2^n</math> states. This is the [[subset construction]] by [[Michael O. Rabin|Rabin]] and [[Dana Scott|Scott]],
| last = Lupanov
| first = Oleg B.
Line 46 ⟶ 45:
}}</ref>
* UFA to DFA: <math>2^n</math> states, see [[Hing Leung|Leung]],<ref name="Leung2005">{{cite journal|last1=Leung|first1=Hing|title=Descriptional complexity of NFA of different ambiguity|journal=International Journal of Foundations of Computer Science|volume=16|issue=
* NFA to UFA: <math>2^n-1</math> states, see Leung.<ref name="Leung2005" /> There was an earlier smaller lower bound by Schmidt.<ref name="Schmidt1978" />
* SVFA to DFA: <math>\Theta(3^{n/3})</math> states, see Jirásková and [[Giovanni Pighizzini|Pighizzini]]<ref name="JiráskováPighizzini2011">{{cite journal|last1=Jirásková|first1=Galina|last2=Pighizzini|first2=Giovanni|title=Optimal simulation of self-verifying automata by deterministic automata|journal=Information and Computation|volume=209|issue=3|year=2011|pages=528–535|issn=0890-5401|doi=10.1016/j.ic.2010.11.017}}</ref>
* 2DFA to DFA: <math>n(n^n-(n-1)^n)</math> states, see [[Christos Kapoutsis|Kapoutsis]].<ref name="Kapoutsis2005">{{Cite book|last1=Kapoutsis|first1=Christos|title=Mathematical Foundations of Computer Science 2005|series=Lecture Notes in Computer Science|volume=3618|year=2005|pages=544–555|issn=0302-9743|doi=10.1007/11549345_47|isbn=978-3-540-28702-5|chapter=Removing Bidirectionality from Nondeterministic Finite Automata}}</ref> Earlier construction by [[John Cedric Shepherdson|Shepherdson]]<ref name="Shepherdson1959">{{cite journal|last1=Shepherdson|first1=J. C.|title=The Reduction of Two-Way Automata to One-Way Automata|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=198–200|issn=0018-8646|doi=10.1147/rd.32.0198}}</ref> used more states, and an earlier lower bound by Moore<ref name="Moore1971">{{cite journal|last1=Moore|first1=F.R.|title=On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata|journal=IEEE Transactions on Computers|volume=C-20|issue=10|year=1971|pages=1211–1214|issn=0018-9340|doi=10.1109/T-C.1971.223108|s2cid=206618275}}</ref> was smaller.
* 2DFA to NFA: <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>, see Kapoutsis.<ref name="Kapoutsis2005" /> Earlier construction by [[Jean-Camille Birget|Birget]]<ref name="Birget1993a">{{cite journal|last1=Birget|first1=Jean-Camille|title=State-complexity of finite-state devices, state compressibility and incompressibility|journal=Mathematical Systems Theory|volume=26|issue=3|year=1993|pages=237–269|issn=0025-5661|doi=10.1007/BF01371727|s2cid=20375279}}</ref> used more states.
* 2NFA to NFA: <math>\binom{2n}{n+1}</math>, see Kapoutsis.<ref name="Kapoutsis2005" />
** 2NFA to NFA accepting the complement: <math>O(4^n)</math> states, see [[Moshe Vardi|Vardi]].<ref name="Vardi1989">{{cite journal|last1=Vardi|first1=Moshe Y.|title=A note on the reduction of two-way automata to one-way automata|journal=Information Processing Letters|volume=30|issue=5|year=1989|pages=261–264|issn=0020-0190|doi=10.1016/0020-0190(89)90205-6|citeseerx=10.1.1.60.464}}</ref>
* AFA to DFA: <math>2^{2^n}</math> states, see [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243|s2cid=238863413|doi-access=free}}</ref>
* AFA to
* 2AFA to DFA: <math>2^{n2^n}</math>, see [[Richard E. Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref>
*
===The 2DFA vs. 2NFA problem and logarithmic space===
{{unsolved|computer science|Does every <math>n</math>-state 2NFA have an equivalent <math>\operatorname{poly}(n)</math>-state 2DFA?}}
It is an open problem whether all 2NFAs can be converted to 2DFAs
with polynomially many states, i.e. whether there is a polynomial <math>p(n)</math>
such that for every <math>n</math>-state 2NFA
there exists a <math>p(n)</math>-state 2DFA.
The problem was raised by Sakoda and [[Michael Sipser|Sipser]],<ref>{{cite conference
|
| first1 = William J.
| last1 = Sakoda
| first2 = Michael
| last2 = Sipser
| title = Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78
| year = 1978
| conference = STOC 1978
| publisher = ACM
| ___location =
| pages =
| doi = 10.1145/800133.804357
| doi-access = free
}}</ref>
who compared it to the [[P vs. NP]] problem
in the [[computational complexity theory]].
Line 108 ⟶ 100:
| volume = 55
| issue = 2
| pages =
| doi = 10.1007/s00224-013-9465-0
| s2cid = 14808151
}}</ref>
Line 120 ⟶ 113:
* for each m-state X-automaton A and n-state X-automaton B there is an <math>f(m,n)</math>-state X-automaton for <math>L(A) \circ L(B)</math>, 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 <math>L(A) \circ L(B)</math> must have at least <math>f(m,n)</math> states.
Line 132 ⟶ 124:
| date = 1970
| title = Estimates of the number of states of finite automata
| journal = Soviet Mathematics - Doklady
| volume = 11
| pages =
}}</ref>
and by Yu, Zhuang and [[Kai Salomaa|Salomaa]].
<ref name="YuZhuang1994">{{cite journal|last1=Yu|first1=Sheng|last2=Zhuang|first2=Qingyu|last3=Salomaa|first3=Kai|title=The state complexities of some basic operations on regular languages|journal=Theoretical Computer Science|volume=125|issue=2|year=1994|pages=315–328|issn=
[[Markus Holzer|Holzer]] and [[Martin Kutrib|Kutrib]]
<ref name="HolzerKutrib2003">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=
pioneered the state complexity of operations on NFA.
The known results for basic operations are listed below.
Line 147 ⟶ 139:
If language <math>L_1</math> requires m states
and language <math>L_2</math> requires n states,
how many states does <math>L_1 \cup L_2</math>
* DFA: <math>mn</math> states, see Maslov<ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>m+n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: at least <math>\min(n,m)^{\Omega(\log(\min(n,m)))}</math>;<ref name="GoosKieferYuan2022" /> between <math>mn+m+n</math> and <math>m + nm 2^{0.79m}</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016">{{Cite book|last1=Jirásek|first1=Jozef|title=Operations on Unambiguous Finite Automata|last2=Jirásková|first2=Galina|last3=Šebej|first3=Juraj|volume=9840|year=2016|pages=243–255|issn=0302-9743|doi=10.1007/978-3-662-53132-7_20|series=Lecture Notes in Computer Science|isbn=978-3-662-53131-0}}</ref>
*
* 2DFA: between <math>m+n</math> and <math>4m+n+4</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State complexity of operations on two-way finite automata over a unary alphabet|journal=Theoretical Computer Science|volume=449|year=2012|pages=106–118|issn=0304-3975|doi=10.1016/j.tcs.2012.04.010|doi-access=free}}</ref>
*
===Intersection===
How many states does <math>L_1 \cap L_2</math>
* DFA: <math>mn</math> states, see Maslov<ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>mn</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: <math>mn</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />
* SVFA: <math>mn</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />
* 2DFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />
===Complementation===
If language L requires n states
then how many states does its ''[[complementation of automata|complement]]''
* DFA: <math>n</math> states, by exchanging accepting and rejecting states.
* NFA: <math>2^n</math> states, see Birget.<ref name="Birget1993b">{{cite journal|last1=Birget|first1=Jean-Camille|title=Partial orders on words, minimal elements of regular languages, and state complexity|journal=Theoretical Computer Science|volume=119|issue=2|year=1993|pages=267–291|issn=0304-3975|doi=10.1016/0304-3975(93)90160-U}}</ref> or Jirásková<ref>{{Cite journal |last=Jirásková |first=Galina |date=2005 |title=State complexity of some operations on binary regular languages |url=https://linkinghub.elsevier.com/retrieve/pii/S0304397504006577 |journal=Theoretical Computer Science |language=en |volume=330 |issue=2 |pages=287–298 |doi=10.1016/j.tcs.2004.04.011}}, Theorem 5</ref>
* UFA: at least <math>n^{\tilde{\Omega}(\log n)}</math> states, see Göös, Kiefer and Yuan,<ref name="GoosKieferYuan2022">{{cite arXiv |last1=Göös |first1=Mika |last2=Kiefer |first2=Stefan |last3=Yuan |first3=Weiqiang |title=Lower Bounds for Unambiguous Automata via Communication Complexity |date=12 February 2022 |class=cs.FL |eprint=2109.09155}}</ref> (this follows an earlier bound by Raskin<ref>{{Cite journal |last=Raskin |first=Mikhail |date=2018 |title=A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 |language=en |publisher=Schloss-Dagstuhl - Leibniz Zentrum für Informatik |doi=10.4230/LIPIcs.ICALP.2018.138|doi-access=free }}</ref>); and at most <math>\sqrt{n+1} \cdot 2^{0.5n}</math> states, see Indzhev and Kiefer.<ref>{{cite journal |last1=Indzhev |first1=Emil |last2=Kiefer |first2=Stefan |title=On complementing unambiguous automata and graphs with many cliques and cocliques |journal=Information Processing Letters |date=1 August 2022 |volume=177 |page=106270 |doi=10.1016/j.ipl.2022.106270 |s2cid=234741832 |url=https://ora.ox.ac.uk/objects/uuid:a36b96e8-fa8e-4ef9-b45b-2a625366cf54/files/rrj4305198 |access-date=29 May 2022 |ref=IndzhevKiefer22 |language=en |issn=0020-0190|doi-access=free |arxiv=2105.07470 }}</ref>
* SVFA: <math>n</math> states, by exchanging accepting and rejecting states.
*
===Concatenation===
How many states does <math>L_1 L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}</math>
* DFA: <math>m \cdot 2^n - 2^{n-1}</math> states, see Maslov <ref name="Maslov" /> and Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>m+n</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: <math>\frac{3}{4} 2^{m+n}-1</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />
* SVFA: <math>\Theta(3^{n/3}2^m)</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />
* 2DFA: at least <math>\frac{2^{\Omega(n)}}{\log m}</math> and at most <math>2m^{m+1}\cdot 2^{n^{n+1}}</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008">{{
===Kleene star===
* DFA: <math>\frac{3}{4} 2^n</math> states, see Maslov<ref name="Maslov" /> and Yu, Zhuang and Salomaa.
* NFA: <math>n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: <math>\frac{3}{4} 2^n</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />
* SVFA: <math>\frac{3}{4}2^n</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />
* 2DFA: at least <math>\frac{1}{n}2^{\frac{n}{2}-1}</math> and at most <math>2^{O(n^{n+1})}</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008" />
===Reversal===
* DFA: <math>2^n</math> states, see Mirkin,<ref name="Mirkin1966">{{cite journal|last1=Mirkin|first1=Boris G.|title=On dual automata|journal=Cybernetics|volume=2|year=1966|pages=6–9|doi=10.1007/bf01072247|s2cid=123186223}}</ref> Leiss,<ref name="Leiss1985">{{cite journal|last1=Leiss|first1=Ernst|title=Succinct representation of regular languages by boolean automata II|journal=Theoretical Computer Science|volume=38|year=1985|pages=133–136|issn=
* NFA: <math>n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: <math>n</math> states.
* SVFA: <math>2n+1</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />
* 2DFA: between <math>n+1</math> and <math>n+2</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008" />
==Finite automata over a unary alphabet==
State complexity of finite automata with a one-letter (''unary'') alphabet, pioneered by [[Marek Chrobak|Chrobak]],<ref name="Chrobak1986">{{cite journal|last1=Chrobak|first1=Marek|title=Finite automata and unary languages|journal=Theoretical Computer Science|volume=47|year=1986|pages=149–158|issn=0304-3975|doi=10.1016/0304-3975(86)90142-8}}</ref> is different from the multi-letter case.
Let <math>g(n)=e^{\Theta(\sqrt{n \ln n})}</math> 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: <math>g(n)+O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2DFA to DFA: <math>g(n)+O(n)</math> states, see Chrobak<ref name="Chrobak1986" /> and Kunc and Okhotin.<ref name="KuncOkhotin2011b">{{Cite book|last1=Kunc|first1=Michal|title=Developments in Language Theory|last2=Okhotin|first2=Alexander|volume=6795|year=2011|pages=324–336|issn=0302-9743|doi=10.1007/978-3-642-22321-1_28|series=Lecture Notes in Computer Science|isbn=978-3-642-22320-4|citeseerx=10.1.1.616.8835}}</ref>
* 2NFA to DFA: <math>O(g(n))</math> states, see Mereghetti and [[Giovanni Pighizzini|Pighizzini]].<ref name="MereghettiPighizzini2001">{{cite journal|last1=Mereghetti|first1=Carlo|last2=Pighizzini|first2=Giovanni|title=Optimal Simulations between Unary Automata|journal=SIAM Journal on Computing|volume=30|issue=6|year=2001|pages=1976–1992|issn=0097-5397|doi=10.1137/S009753979935431X|hdl=2434/35121|hdl-access=free}}</ref> and [[Viliam Geffert|Geffert]], Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Converting two-way nondeterministic unary automata into simpler automata|journal=Theoretical Computer Science|volume=295|issue=1–3|year=2003|pages=189–203|issn=0304-3975|doi=10.1016/S0304-3975(02)00403-6}}</ref>
* NFA to 2DFA: at most <math>O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2NFA to 2DFA: at most <math>n^{O(\log n)}</math> states, proved by implementing the method of [[Savitch's theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003" />
* UFA to DFA: <math>e^{\Theta(\sqrt[3]{n (\ln n)^2})}</math>, see Okhotin.<ref name="Okhotin2012">{{cite journal|last1=Okhotin|first1=Alexander|title=Unambiguous finite automata over a unary alphabet|journal=Information and Computation|volume=212|year=2012|pages=15–36|issn=0890-5401|doi=10.1016/j.ic.2012.01.003|doi-access=free}}</ref>
* NFA to UFA: <math>g(n)+O(n^2)</math>, see Okhotin.<ref name="Okhotin2012" />
===Union===
* DFA: <math>mn</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>m+n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 2DFA: between <math>m+n</math> and <math>2m+n+4</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012"/>
* 2NFA: <math>m+n</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />
===Intersection===
* DFA: <math>mn</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>mn</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 2DFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />
===Complementation===
* DFA: <math>n</math> states.
* NFA: <math>g(n)+O(n^2)</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: at least <math>n^{(\log \log \log n)^{\Theta(1)}}</math> states, see Raskin,<ref name="Raskin2018">{{cite conference |last1=Raskin|first1=Michael|title=A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton|pages=138:1–138:11|book-title=Proc. ICALP 2018|year=2018|doi=10.4230/LIPIcs.ICALP.2018.138|doi-access=free }}</ref> and at most <math>e^{\Theta(\sqrt[3]{n (\ln n)^2})}</math> states, see Okhotin.<ref name="Okhotin2012" />
* 2DFA: at least <math>n</math> and at most <math>2n+3</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: at least <math>n</math> and at most <math>O(n^8)</math> states. The upper bound is by implementing the method of the [[Immerman–Szelepcsényi theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007"/>
===Concatenation===
* DFA: <math>mn</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: between <math>m+n-1</math> and <math>m+n</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 2DFA: <math>e^{\Theta(\sqrt{(m+n)\log(m+n)})}</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: <math>e^{\Theta(\sqrt{(m+n)\log(m+n)})}</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
===Kleene star===
* DFA: <math>(n-1)^2+1</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: <math>(n-1)^2+1</math> states, see Okhotin.<ref name="Okhotin2012" />
* 2DFA: <math>\Theta((g(n))^2)</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: <math>\Theta(g(n))</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
==Further reading==
Line 224 ⟶ 257:
was written by Yu.-->
Surveys of state complexity
were written by Holzer and Kutrib<ref name="HolzerKutrib2009">{{cite journal|last1=Holzer|first1=Markus|last2=Kutrib|first2=Martin|title=Nondeterministic finite automata — recent results on the descriptional and computational complexity|journal=International Journal of Foundations of Computer Science|volume=20|issue=
and by Gao et al.<ref>{{cite arXiv| eprint=1509.03254v1| last1=Gao| first1=Yuan| title=A Survey on Operational State Complexity| last2=Moreira| first2=Nelma| last3=Reis| first3=Rogério| last4=Yu| first4=Sheng| class=cs.FL| year=2015}}</ref>
New research on state complexity
Line 237 ⟶ 270:
{{reflist}}
[[Category:Finite-state
| |||