In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton.
(q,a,q1\veeq2)
q1
q2
(q,a,q1\wedgeq2)
q1
q2
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 deterministic finite automaton (DFA), hence AFAs accept exactly the regular languages.
An alternative model which is frequently used is the one where Boolean combinations are in disjunctive normal form so that, e.g.,
\{\{q1\},\{q2,q3\}\}
q1\vee(q2\wedgeq3)
\{\emptyset\}
\emptyset
Alternating finite automata can be extended to accept trees in the same way as tree automata, yielding alternating tree automata.
An alternating finite automaton (AFA) is a 5-tuple,
(Q,\Sigma,q0,F,\delta)
Q
\Sigma
q0\inQ
F\subseteqQ
\delta\colonQ x \Sigma x \{0,1\}Q\to\{0,1\}
For each string
w\in\Sigma*
Aw\colonQ\to\{0,1\}
w
A\epsilon(q)=1
q\inF
A\epsilon(q)=0
Aaw(q)=\delta(q,a,Aw)
The automaton accepts a string
w\in\Sigma*
Aw(q0)=1
This model was introduced by Chandra, Kozen and Stockmeyer.[1]
See main article: article and State complexity.
Even though AFA can accept exactly the regular languages, they are different from other types of finite automata in the succinctness of description, measured by the number of their states.
Chandra et al. proved that converting an
n
2n | |
2 |
2n
n
2n
The membership problem asks, given an AFA
A
w
A
w
The non-emptiness problem (is the language of an input AFA non-empty?), the universality problem (is the complement of the language of an input AFA empty?), and the equivalence problem (do two input AFAs recognize the same language) are PSPACE-complete for AFAs.
. Theories of Computability . Nick Pippenger . . 1997 . 978-0-521-55380-3 .