# 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 ,
*A*nondeterministically chooses to switch the state to either or , reading*a*. Thus, behaving like a regular nondeterministic finite automaton. - For a universal transition ,
*A*moves to**and**, 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 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 Disjunctive Normal Form so that would represent . The state **tt** (*true*) is represented by in this case and **ff** (*false*) by .
This clause representation is usually more efficient.

## Formal Definition

An alternating finite automaton (AFA) is a 6-tuple, , where

- is a finite set of existential states. Also commonly represented as .
- is a finite set of universal states. Also commonly represented as .
- is a finite set of input symbols.
- is a set of transition functions to next state .
- is the initial (start) state, such that .
- is a set of accepting (final) states such that .

## References

- {{#invoke:citation/CS1|citation

|CitationClass=book }}