NFA

From CS2800 wiki


A Nondeterministic Finite Automaton M is a 5-tuple M = (Q,Σ,δ,q0,A), where
  • Q is a finite set, called the set of states of M;
  • Σ is a finite set called the alphabet of M (elements of Σ are called characters)
  • δ is a function [math]δ:Q×Σ→2^Q [/math], called the transition function. There is a transition from q to q′ on input a if [math]q' \href{/cs2800/wiki/index.php/%5Cin}{\in} δ(q,a) [/math]. [math]q_0\href{/cs2800/wiki/index.php/%E2%88%88}{∈}Q [/math] is the start state
  • [math]A⊆Q [/math] is the set of accepting states"

Compared to DFAs

[math]\delta [/math]

DFAs require exactly one transition from every state on every character (δ is a function). While processing a string, there is only one place you can go at every step.

Nondeterministic finite automata (NFAs) allow any number of transitions from a state on a given character. The machine accepts a string xx if there is any possible path from the start state to a final state using xx.

One way of thinking of nondeterminism is that the machine gets to "magically" guess which path to take at any point.

Another way is that it explores all possible paths and accepts if any of them do.

Formally, the only difference between an NFA and a DFA is that in an NFA, δδ is a function from Q×ΣQ×Σ to 2Q2Q (instead of to QQ). δ(q,a)δ(q,a) outputs the set of states that can be reached by taking a transition labeled aa from state qq.

The extended transition function serves the same purpose as with a DFA. The definition is a bit more involved, but follows the same logic: to compute δ^(q,xa)δ^(q,xa), first recursively find all of the states you can reach from qq using string xx: compute δ^(q,x)δ^(q,x). Then, from each of these steps, take all of the states you can reach from any of them using a single transition on aa. Formally: