Alternating finite automaton

Wiki is stupid. Your stupid too. 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.

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 DNF so that $\{\{q_{1}\}\{q_{2},q_{3}\}\}$ would represent $q_{1}\vee (q_{2}\wedge q_{3})$. The state tt (true) is represented by $\{\{\}\}$ in this case and ff (false) by $\emptyset$. This clause representation is usually more efficient.