# Alternating finite automaton

(Redirected from Alternating 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})}$, 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 represented as clauses. For instance, one could assume the combinations to be in disjunctive normal form so that ${\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 \{\{\}\}}$ in this case and ff (false) by ${\displaystyle \varnothing }$. This clause representation is usually more efficient.

## Formal Definition

An alternating finite automaton (AFA) is a 6-tuple, ${\displaystyle (S(\exists ),S(\forall ),\Sigma ,\delta ,P_{0},F)}$, where

• ${\displaystyle S(\exists )}$ is a finite set of existential states. Also commonly represented as ${\displaystyle S(\vee )}$.
• ${\displaystyle S(\forall )}$ is a finite set of universal states. Also commonly represented as ${\displaystyle S(\wedge )}$.
• ${\displaystyle \ \Sigma }$ is a finite set of input symbols.
• ${\displaystyle \ \delta }$ is a set of transition functions to next state ${\displaystyle (S(\exists )\cup S(\forall ))\times (\Sigma \cup \{\varepsilon \})\to 2^{S(\exists )\cup S(\forall )}}$.
• ${\displaystyle \ P_{0}}$ is the initial (start) state, such that ${\displaystyle P_{0}\in S(\exists )\cup S(\forall )}$.
• ${\displaystyle \ F}$ is a set of accepting (final) states such that ${\displaystyle F\subseteq S(\exists )\cup S(\forall )}$.

The model was introduced by Chandra, Kozen and Stockmeyer.[1]

## State complexity

Main article: State complexity

Even though AFA can accept exactly the regular languages, they are different from other types of finite automata in the succinctness of description, measured by the number of their states.

Chandra et al.[1] proved that converting an ${\displaystyle n}$-state AFA to an equivalent DFA requires ${\displaystyle 2^{2^{n}}}$ states in the worst case. Another construction by Fellah, Jürgensen and Yu.[2] converts an AFA with ${\displaystyle n}$ states to a nondeterministic finite automaton (NFA) with up to ${\displaystyle 2^{n}}$ states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.

## References

1. ^ a b Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternation". Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. ISSN 0004-5411.
2. ^ Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Constructions for alternating finite automata∗". International Journal of Computer Mathematics. 35 (1-4): 117–132. doi:10.1080/00207169008803893. ISSN 0020-7160.