Alternating finite automaton

• For an existential transition ${\displaystyle (q,a,q_1\vee q_2)}$, A nondeterministically chooses to switch the state to either ${\displaystyle q_1}$ or ${\displaystyle q_2}$, reading a. Thus, behaving like a regular nondeterministic finite automaton.
• For a universal transition ${\displaystyle (q,a,q_1\wedge q_2)}$, A moves to ${\displaystyle q_1}$ and ${\displaystyle q_2}$, 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 which 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 \{\mathrm{\varnothing }\}}$ in this case and ff (false) by ${\displaystyle \mathrm{\varnothing }}$. 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.

Formal definition

An alternating finite automaton (AFA) is a 5-tuple, ${\displaystyle (Q,\mathrm{\Sigma },q_0,F,\delta )}$, where

• ${\displaystyle Q}$ is a finite set of states;
• ${\displaystyle \mathrm{\Sigma }}$ is a finite set of input symbols;
• ${\displaystyle q_0\in Q}$ is the initial (start) state;
• ${\displaystyle F\subseteq Q}$ is a set of accepting (final) states;
• ${\displaystyle \delta :Q\times \mathrm{\Sigma }\times \{0,1{\}}^Q\to \{0,1\}}$ is the transition function.

For each string ${\displaystyle w\in {\mathrm{\Sigma }}^{\ast }}$, we define the acceptance function ${\displaystyle A_w:Q\to \{0,1\}}$ by induction on the length of ${\displaystyle w}$:

• ${\displaystyle A_{ϵ}(q)=1}$ if ${\displaystyle q\in F}$, and ${\displaystyle A_{ϵ}(q)=0}$ otherwise;
• ${\displaystyle A_{aw}(q)=\delta (q,a,A_w)}$.

The automaton accepts a string ${\displaystyle w\in {\mathrm{\Sigma }}^{\ast }}$ if and only if ${\displaystyle A_w(q_0)=1}$.

This model was introduced by Chandra, Kozen and Stockmeyer.