1
$\begingroup$

Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and that from Q∀ are 'and'ed.

Is there an algorithm for converting AFA to ε-NFA, NFA or DFA? I tried searching in Google, but all I get is conversions between ε-NFA, NFA and DFA. I didn't get any more resources about AFA.

Improve this question
$\endgroup$
4
  • $\begingroup$ The proof that AFAs accept regular languages might be constructive. Have you looked at one? $\endgroup$
    – Yuval Filmus
    May 16 at 20:24
  • 3
    $\begingroup$ In the document you link, Theorem 6 defines a nondeterministic finite state automaton that is equivalent to a given alternating finite automaton. (That is probably the algorithm you are looking for.) In a way this construction uses the computation tree, merging branches that are equivalent. In a way this is similar to the construction of a DFA for an NFA, as that construction also collects all states that can be reached. $\endgroup$
    – Hendrik Jan
    May 16 at 21:05
  • $\begingroup$ @HendrikJan I tried to go through that, though I don't quite fully understand it. δ′(X, a) = {X′ ⊆ δ(X, a) | ∀q ∈ X ∩ Q∀. δ(q, a) ⊆ X′ ∧ ∀q ∈ X ∩ Q∃. X′ ∩ δ(q, a) ≠ ∅}. In this, what is X and X′? Is it states? or set of states? $\endgroup$
    – Sourav Kannantha B
    May 17 at 13:20
  • $\begingroup$ Sets of states, see my extended answer with some of the intuition in that construction. $\endgroup$
    – Hendrik Jan
    May 17 at 20:54

1 Answer 1

Reset to default
3
$\begingroup$

The construction yields a nondeterministic NFA $A'$ that is equivalent to the original alternating AFA $A$.

The states of the new automaton are sets of states of $A$, just as in the classic construction of a deterministic DFA from an NFA. In the new DFA we collect all reachable states and accept if one of the states in this set is accepting in the original NFA.

Here the situation is dual: we accept in a state $X$ if all states are accepting in the original AFA: $X\subseteq F$, or in other words $X\in 2^F\setminus \{\varnothing\}$. From a set $X$ we move (nondeterministically) to a new set $X'$. For each $q\in X$ we do the following.

  1. If $q\in Q_\forall$ is universal, then all successor states $\delta(q,a)$ must lead to acceptance, so all of them are part of the new state $\delta(q,a) \subseteq X'$.

  2. If $q\in Q_\exists$ is existential, then at least one of the successor states $\delta(q,a)$ must be accepting, so at least one of those states must be in the new state: $\delta(q,a) \cap X' \neq \varnothing$.

This construction keeps track of the computation tree, but when states occur more than one time in that tree they are collapsed into one. See this figure from the paper you linked (K. Narayan Kumar, Chennai Mathematical Institute, Notes on Automata, Logic, Games and Algebra, Lecture 6: Alternating Automata):

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the explanation. This cleared up all my doubts. I have to work on this a bit to be sure. $\endgroup$
    – Sourav Kannantha B
    May 19 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.