Definition of a Nondeterministic Accepter
Nondeterminism means a choice of moves for an automaton. Rather than
prescribing a unique move in each situation, we allow a set of possible moves.
Formally, we achieve this by defining the transition function so that its range is a
set of possible states.
Definition 2.4
A nondeterministic finite accepter or nfa is defined by the quintuple
M=(Q,Σ,δ,q 0 ,F),
where Q,Σ,q 0 ,F are defined as for deterministic finite accepters, but
Note that there are three major differences between this definition and the
definition of a dfa. In a nondeterministic accepter, the range of δ is in the
powerset 2 Q , so that its value is not a single element of Q but a subset of it. This
subset defines the set of all possible states that can be reached by the transition.
If, for instance, the current state is q 1 , the symbol a is read, and
δ(q 1 ,a) = {q 0 ,q 2 } :
then either q 0 or q 2 could be the next state of the nfa. Also, we allow λ as the
second argument of δ. This means that the nfa can make a transition without
consuming an input symbol. Although we still assume that the input mechanism
can only travel to the right, it is possible that it is stationary on some moves.
Finally, in an nfa, the set δ (q i ,a) may be empty, meaning that there is no
transition defined for this specific situation.
Like dfa's, nondeterministic accepters can be represented by transition
graphs. The vertices are determined by Q, while an edge (q i ,q j ) with label a is in
the graph if and only if δ (q i ;a) contains q j . Note that since a may be the empty
string, there can be some edges labeled λ.
Nondeterminism means a choice of moves for an automaton. Rather than
prescribing a unique move in each situation, we allow a set of possible moves.
Formally, we achieve this by defining the transition function so that its range is a
set of possible states.
Definition 2.4
A nondeterministic finite accepter or nfa is defined by the quintuple
M=(Q,Σ,δ,q 0 ,F),
where Q,Σ,q 0 ,F are defined as for deterministic finite accepters, but
Note that there are three major differences between this definition and the
definition of a dfa. In a nondeterministic accepter, the range of δ is in the
powerset 2 Q , so that its value is not a single element of Q but a subset of it. This
subset defines the set of all possible states that can be reached by the transition.
If, for instance, the current state is q 1 , the symbol a is read, and
δ(q 1 ,a) = {q 0 ,q 2 } :
then either q 0 or q 2 could be the next state of the nfa. Also, we allow λ as the
second argument of δ. This means that the nfa can make a transition without
consuming an input symbol. Although we still assume that the input mechanism
can only travel to the right, it is possible that it is stationary on some moves.
Finally, in an nfa, the set δ (q i ,a) may be empty, meaning that there is no
transition defined for this specific situation.
Like dfa's, nondeterministic accepters can be represented by transition
graphs. The vertices are determined by Q, while an edge (q i ,q j ) with label a is in
the graph if and only if δ (q i ;a) contains q j . Note that since a may be the empty
string, there can be some edges labeled λ.