Content deleted Content added
grammar fix |
unary UFAs |
||
Line 164:
* 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>
* UFA: at least <math>n^{2-o(1)}</math> and at most <math>\sqrt{n+1} \cdot 2^{0.5n}</math> states, 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}}</ref> for the lower bound and Indzhev and Kiefer<ref name="EmilKiefer2021">{{cite arXiv|last1=Indzhev|first1=Emil|last2=Kiefer|first2=Stefan|eprint=2105.07470|title=On Complementing Unambiguous Automata and Graphs With Many Cliques and Cocliques|class=cs.FL|date=2021}}</ref> for the upper
* SVFA: <math>n</math> states, by exchanging accepting and rejecting states.
* 2DFA: at least <math>n</math> and at most <math>4n</math> states, see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Complementing two-way finite automata|journal=Information and Computation|volume=205|issue=8|year=2007|pages=1173–1187|issn=0890-5401|doi=10.1016/j.ic.2007.01.008}}</ref>
Line 170:
===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" />
Line 229:
* 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^{
* 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"/>
|