Added to Favorites

Related Searches

Nearby Words

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.## Formal Definition

- 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 an NFA to a deterministic finite automaton (DFA). This construction converts an AFA with k states to an 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.

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)$.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday January 26, 2008 at 17:40:37 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Saturday January 26, 2008 at 17:40:37 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.