Definitions

# 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 $\left(q, a, q_1 vee q_2\right)$, A nondeterministically chooses to switch the state to either $q_1$ or $q_2$, reading a. Thus, behaving like a regular nondeterministic finite automaton.
• For a universal transition $\left(q, a, q_1 wedge q_2\right)$, A moves to $q_1$ and $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 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 an NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to an 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 $\left\{\left\{q_1\right\}\left\{q_2,q_3\right\}\right\}$ would represent $q_1 vee \left(q_2 wedge q_3\right)$. The state tt (true) is represented by $\left\{\left\{\right\}\right\}$ in this case and ff (false) by $emptyset$. This clause representation is usually more efficient.

## Formal Definition

An alternating finite automaton (AFA) is a 6-tuple, $\left(S\left(exists\right), S\left(forall\right), Sigma, delta, P_0, F\right)$, where

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

Search another word or see finite automatonon Dictionary | Thesaurus |Spanish