Alternating finite automaton

In automata theory, an alternating finite automaton (AFA) is a non-deterministic finite automaton whose transitions are divided into existential and universal transitions. Let A be an alternating automaton.

For a transition $(q, a, q_1 \vee q_2)$ , A nondeterministically chooses to switch the state to either $q 1$ or $q 2$ , reading a.
For a transition $(q, a, q_1 \wedge q_2)$ , A moves to $q 1$ and $q 2$ , reading a.

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 tells that any AFA is equivalent to an non-deterministic finite automaton (NFA) by performing a similar kind of powerset construction as it is used for the transformation of a NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to a NFA with up to $2 k$ states.

Categories: Computational models