Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Alternating finite automaton
Summary
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.
For an existential transition , A nondeterministically chooses to switch the state to either or , reading a. Thus, behaving like a regular nondeterministic finite automaton.
For a universal transition , A moves to and , 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., would represent . The state tt (true) is represented by in this case and ff (false) by . 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.
An alternating finite automaton (AFA) is a 6-tuple,
where
is a finite set of existential states. Also commonly represented as .
is a finite set of universal states. Also commonly represented as .
is a finite set of input symbols.
is a set of transition relations to next state .
is the initial (start) state, such that .
is a set of accepting (final) states such that .
The model was introduced by Chandra, Kozen and Stockmeyer.
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 -state AFA to an equivalent DFA
requires states in the worst case. Another construction by Fellah, Jürgensen and Yu.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.