alternating finite automaton

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 $q_1$ or $q_2$ , reading a.
For a transition $(q, a, q_1 \wedge q_2)$ , A moves to $q_1$ and $q_2$ , 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.

<< Previous

Word Browser

Next >>

jmijrvi
octavius
winchester magnum
aortic aneurysm
phagemid
jrvenp
zvonimir boban
and the ass saw the angel
battle of jieqiao
teardrop
giorgos karagounis

xenotransplantation
gossip girl
lineman's handset
dsa (disambiguation)
bsd daemon
jrt
vrba
jones in the fast lane
7 notas 7 colores
sardana
zmeu

super cannes
apa sambetei
bounding sphere
la boca
mesterul manole
mandira bedi
apa vie
spiridus
saratoga, new south wales
mission control center
taslim olawale elias

roy goode
william greenleaf eliot
elipando
hintlesham
james dunn (actor)
stephen benton elkins
glen waverley railway line, melbourne
allen j. ellender
george f. elliott
james elliott
james william elliott