Two-way finite automaton: Difference between revisions

Revision as of 18:17, 15 March 2017

Revision as of 21:53, 25 March 2017

Line 49:

== Two-way nondeterministic finite automaton ==

A ''two-way nondeterministic finite automaton'' (2NFA) may have multiple transitions defined in the same configuration. Its transition function is

* <math>\delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow 2^{Q \times \{left,right\}}</math>.

Like a standard one-way [[Nondeterministic finite automaton|NFA]], a 2NFA accepts a string if at least one of the possible computations is accepting. Like the 2DFAs, the 2NFAs also accept only regular languages.

==Two-way alternating finite automaton==

A '''two-way alternating finite automaton''' (2AFA) is a two-way extension of an [[alternating finite automaton]] (AFA). Its state set is

* <math>Q=Q_\exists \cup Q_\forall</math> where <math>Q_\exists \cap Q_\forall=\emptyset</math>.

States in <math>Q_\exists</math> and <math>Q_\forall</math> are called ''existential'' resp. ''universal''. In an existential state a 2AFA nondeterministically chooses the next state like an NFA, and accepts if at least one of the resulting computations accepts. In a universal state 2AFA moves to all next states, and accepts if all the resulting computations accept.

==State complexity tradeoffs==

{{Main|State complexity}}

Two-way and one-way finite automata, deterministic and nondeterministic and alternating, accept the same class of regular languages. However, transforming an automaton of one type to an equivalent automaton of another type incurs a blow-up in the number of states. [[Christos Kapoutsis|Kapoutsis]]<ref>{{cite conference

| title = Removing Bidirectionality from Nondeterministic Finite Automata

| first = Christos

Line 69 ⟶ 77:

| pages = 544–555

| doi = 10.1007/11549345_47

}}</ref> determined that transforming an <math>n</math>-state 2DFA to an equivalent DFA requires <math>n(n^n-(n-1)^n)</math> states in the worst case. If an <math>n</math>-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>. [[Richard 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>

proved that an <math>n</math>-state 2AFA can be converted to a DFA with <math>2^{n2^n}</math> states.

The 2AFA to NFA conversion requires <math>2^{\Theta(n \log n)}</math> states in the worst case,

see [[Viliam Geffert|Geffert]] and [[Alexander Okhotin|Okhotin]].<ref name="GeffertOkhotin2014">{{cite journal|last1=Geffert|first1=Viliam|last2=Okhotin|first2=Alexander|title=Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata|volume=8634|year=2014|pages=291–302|issn=0302-9743|doi=10.1007/978-3-662-44522-8_25}}</ref>

{{unsolved|computer science|Does every n-state 2NFA have an equivalent poly(n)-state 2DFA?}}