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.
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 nondeterministic finite automaton (NFA) by performing a similar kind of powerset construction as it is used for the transformation of an NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to an NFA with up to
An alternative model which is frequently used is the one where Boolean combinations are represented as clauses. For instance, one could assume the combinations to be in disjunctive normal form so that
Formal Definition
An alternating finite automaton (AFA) is a 6-tuple,