Alternating finite automaton

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.

• For an existential transition ${\displaystyle (q,a,q_{1}\vee q_{2})}$, the automaton A nondeterministically chooses to switch the state to either ${\displaystyle q_{1}}$ or ${\displaystyle q_{2}}$, upon reading a. Thus, behaving like a regular nondeterministic finite automaton.
• For a universal transition ${\displaystyle (q,a,q_{1}\wedge q_{2})}$, the automaton A moves to ${\displaystyle q_{1}}$ and ${\displaystyle q_{2}}$, upon reading a, simulating the behavior of a parallel machine.

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 that is frequently used is the one where Boolean combinations are in disjunctive normal form so that, e.g., ${\displaystyle \{\{q_{1}\},\{q_{2},q_{3}\}\}}$ would represent ${\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 tree automata, yielding alternating tree automata.