Alternating finite automaton

In <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>, an alternating finite automaton (AFA) is a <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a> whose transitions are divided into <a href="/facts/Existential_quantification/hHveaBYo">existential</a> and <a href="/facts/Universal_quantification/agNmvJKN">universal</a> transitions. For example, let A be an alternating <a href="/facts/Automaton/SXtErQr2">automaton</a>.

<ul><li>For an existential transition 
 
 
 
 (
 q
 ,
 a
 ,
 
 q
 
 1
 
 
 ∨
 
 q
 
 2
 
 
 )
 
 
 {\displaystyle (q,a,q_{1}\vee q_{2})}
 
, A nondeterministically chooses to switch the state to either 
 
 
 
 
 q
 
 1
 
 
 
 
 {\displaystyle q_{1}}
 
 or 
 
 
 
 
 q
 
 2
 
 
 
 
 {\displaystyle q_{2}}
 
, reading a. Thus, behaving like a regular <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a>.</li>
<li>For a universal transition 
 
 
 
 (
 q
 ,
 a
 ,
 
 q
 
 1
 
 
 ∧
 
 q
 
 2
 
 
 )
 
 
 {\displaystyle (q,a,q_{1}\wedge q_{2})}
 
, A moves to 
 
 
 
 
 q
 
 1
 
 
 
 
 {\displaystyle q_{1}}
 
 and 
 
 
 
 
 q
 
 2
 
 
 
 
 {\displaystyle q_{2}}
 
, reading a, simulating the behavior of a parallel machine.</li></ul>
Note that due to the universal quantification a run is represented by a run tree. A accepts a word w, if there exists a run tree on w such that every path ends in an accepting state.
A basic theorem states that any AFA is equivalent to a <a href="/facts/Deterministic_finite_automaton/9conRLFS">deterministic finite automaton</a> (DFA), hence AFAs accept exactly the <a href="/facts/Regular_language/ahxw67T1">regular languages</a>.
An alternative model which is frequently used is the one where Boolean combinations are in <a href="/facts/Disjunctive_normal_form/hsw2pRPu">disjunctive normal form</a> so that, e.g., 
 
 
 
 {
 {
 
 q
 
 1
 
 
 }
 ,
 {
 
 q
 
 2
 
 
 ,
 
 q
 
 3
 
 
 }
 }
 
 
 {\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}
 
 would represent 
 
 
 
 
 q
 
 1
 
 
 ∨
 (
 
 q
 
 2
 
 
 ∧
 
 q
 
 3
 
 
 )
 
 
 {\displaystyle q_{1}\vee (q_{2}\wedge q_{3})}
 
. The state tt (true) is represented by 
 
 
 
 {
 ∅
 }
 
 
 {\displaystyle \{\emptyset \}}
 
 in this case and ff (false) by 
 
 
 
 ∅
 
 
 {\displaystyle \emptyset }
 
. This representation is usually more efficient.
Alternating finite automata can be extended to accept trees in the same way as <a href="/facts/Tree_automaton/Tu9nqDL2">tree automata</a>, yielding <a href="/facts/Alternating_tree_automaton/jNVskYIo">alternating tree automata</a>.

Alternating finite automaton open-in-new

Alternating finite automaton