Alternating finite automaton explained

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.

(q,a,q1\veeq2)

, A nondeterministically chooses to switch the state to either

q1

or

q2

, reading a. Thus, behaving like a regular nondeterministic finite automaton.

(q,a,q1\wedgeq2)

, A moves to

q1

and

q2

, 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 states that any AFA is equivalent to a deterministic finite automaton (DFA), hence AFAs accept exactly the regular languages.

An alternative model which is frequently used is the one where Boolean combinations are in disjunctive normal form so that, e.g.,

\{\{q1\},\{q2,q3\}\}

would represent

q1\vee(q2\wedgeq3)

. The state tt (true) is represented by

\{\emptyset\}

in this case and ff (false) by

\emptyset

. This representation is usually more efficient.

Alternating finite automata can be extended to accept trees in the same way as tree automata, yielding alternating tree automata.

Formal definition

An alternating finite automaton (AFA) is a 5-tuple,

(Q,\Sigma,q0,F,\delta)

, where

Q

is a finite set of states;

\Sigma

is a finite set of input symbols;

q0\inQ

is the initial (start) state;

F\subseteqQ

is a set of accepting (final) states;

\delta\colonQ x \Sigma x \{0,1\}Q\to\{0,1\}

is the transition function.

For each string

w\in\Sigma*

, we define the acceptance function

Aw\colonQ\to\{0,1\}

by induction on the length of

w

:

A\epsilon(q)=1

if

q\inF

, and

A\epsilon(q)=0

otherwise;

Aaw(q)=\delta(q,a,Aw)

.

The automaton accepts a string

w\in\Sigma*

if and only if

Aw(q0)=1

.

This model was introduced by Chandra, Kozen and Stockmeyer.[1]

State complexity

See main article: article and State complexity.

Even though AFA can accept exactly the regular languages, they are different from other types of finite automata in the succinctness of description, measured by the number of their states.

Chandra et al. proved that converting an

n

-state AFA to an equivalent DFArequires
2n
2
states in the worst case, though a DFA for the reverse language can be constructued with only

2n

states. Another construction by Fellah, Jürgensen and Yu.[2] converts an AFA with

n

states to a nondeterministic finite automaton (NFA) with up to

2n

states by performing a similar kind of powerset construction as used for the transformation of an NFA to a DFA.

Computational complexity

The membership problem asks, given an AFA

A

and a word

w

, whether

A

accepts

w

. This problem is P-complete.[3] This is true even on a singleton alphabet, i.e., when the automaton accepts a unary language.

The non-emptiness problem (is the language of an input AFA non-empty?), the universality problem (is the complement of the language of an input AFA empty?), and the equivalence problem (do two input AFAs recognize the same language) are PSPACE-complete for AFAs.

References

. Theories of Computability . Nick Pippenger . . 1997 . 978-0-521-55380-3 .

Notes and References

  1. Chandra. Ashok K.. Kozen. Dexter C.. Stockmeyer. Larry J.. Alternation. Journal of the ACM. 28. 1. 1981. 114–133. 0004-5411. 10.1145/322234.322243. free.
  2. Fellah. A.. Jürgensen. H.. Yu. S.. Constructions for alternating finite automata∗. International Journal of Computer Mathematics. 35. 1–4. 1990. 117–132. 0020-7160. 10.1080/00207169008803893.
  3. Theorem 19 of 2011-03-01. Descriptional and computational complexity of finite automata—A survey. Information and Computation. en. 209. 3. 456–470. 10.1016/j.ic.2010.11.013. 0890-5401. Holzer. Markus. Kutrib. Martin.