Alternating finite automaton

From Wikipedia, the free 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 (q, a, q_1 \vee q_2), A nondeterministically chooses to switch the state to either q1 or q2, reading a.
  • For a transition (q, a, q_1 \wedge q_2), A moves to q1 and q2, 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 2k 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 {{q1}{q2,q3}} 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.

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../a/l/t/Alternating_finite_automaton.html"