In automata theory, an alternating finite automaton (AFA) is a non-deterministic finite automaton whose transitions are divided into existential and universal transitions. Let A be an alternating automaton. Automata theory is a field of computer science which studies finite state machines, by means of mathematical representations of them (automata, Turing machines). ... Afa may refer to: Afa (mythology) in the Polynesian mythology of Samoa Afa (French administration) in Corsica The American Family Association. ... In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. ... In predicate logic, existential quantification is an attempt to formalize the notion that something (a logical predicate) is true for something, or at least one relevant thing. ... In predicate logic, universal quantification is an attempt to formalise the notion that something (a logical predicate) is true for everything, or every relevant thing. ... A drummer automaton An automaton (plural: automata) is a self-operating machine. ...

• For a transition , A nondeterministically chooses to switch the state to either q₁ or q₂, reading a.
• For a transition , A moves to q₁ and q₂, reading a.

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. In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. ... In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is a deterministic next state. ...

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₁}{q₂,q₃}} would represent . The state tt (true) is represented by {{}} in this case and ff (false) by . This clause representation is usually more efficient. In Boolean logic, Disjunctive Normal Form (DNF) is a method of standardizing and normalizing logical formulas. ...