Alternating finite automaton
From Free net encyclopedia
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.
- For a transition <math>(q, a, q_1 \vee q_2)</math>, A nondeterministically chooses to switch the state to either <math>q_1</math> or <math>q_2</math>, reading a.
- For a transition <math>(q, a, q_1 \wedge q_2)</math>, A moves to <math>q_1</math> and <math>q_2</math>, 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 <math>2^k</math> 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 <math>\{\{q_1\}\{q_2,q_3\}\}</math> would represent <math>q_1 \vee (q_2 \wedge q_3)</math>. The state tt (true) is represented by <math>\{\{\}\}</math> in this case and ff (false) by <math>\emptyset</math>. This clause representation is usually more efficient.Template:Compu-sci-stub