Alternating finite automaton

From Wikipedia, the free encyclopedia

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 $(q, a, q_1 \vee q_2)$ , 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 $(q, a, q_1 \wedge q_2)$ , 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 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.

[edit] Formal Definition

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

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