exercise.
With this observation, we have a method for computing δ * (q i ,w). We
evaluate all walks of length at most Λ + (1 + Λ) |w|originating at q i . We select
from them those that are labeled w. The terminating vertices of the selected
walks are the elements of the set δ * (q i ,w).
As we have remarked, it is possible to define δ * in a recursive fashion as was
done for the deterministic case. The result is unfortunately not very, transparent,
and arguments with the extended transition function defined this way are hard to
follow. We prefer to use the more intuitive and more manageable alternative in
Definition 2.5.
As for dfa's, the language accepted by an nfa is defined formally by the
extended transition function.
Definition 2.6
The language L accepted by an nfa M = (Q,Σ,δ, q 0 ,F) is defined as the set of all
strings accepted in the above sense. Formally,
In words, the language consists of all strings w for which there is a walk labeled
w from the initial vertex of the transition graph to some final vertex.
Example 2.10
What is the language accepted by the automaton in Figure 2.9? It is easy to see
from the graph that the only way the nfa can stop in a final state is if the input is
either a repetition of the string 10 or the empty string. Therefore, the automaton
accepts the language L= {(10) n : n ≥0}.
What happens when this automaton is presented with the string w = 110?
After reading the prefix 11, the automaton finds itself in state q 2 , with the
transition δ (q 2 , 0) undefined. We call such a situation a dead configuration, and
we can visualize it as the automaton simply stopping without further action. But
we must always keep in mind that such visualizations are imprecise and carry
with them some danger of misinterpretation. What we can say precisely is that
With this observation, we have a method for computing δ * (q i ,w). We
evaluate all walks of length at most Λ + (1 + Λ) |w|originating at q i . We select
from them those that are labeled w. The terminating vertices of the selected
walks are the elements of the set δ * (q i ,w).
As we have remarked, it is possible to define δ * in a recursive fashion as was
done for the deterministic case. The result is unfortunately not very, transparent,
and arguments with the extended transition function defined this way are hard to
follow. We prefer to use the more intuitive and more manageable alternative in
Definition 2.5.
As for dfa's, the language accepted by an nfa is defined formally by the
extended transition function.
Definition 2.6
The language L accepted by an nfa M = (Q,Σ,δ, q 0 ,F) is defined as the set of all
strings accepted in the above sense. Formally,
In words, the language consists of all strings w for which there is a walk labeled
w from the initial vertex of the transition graph to some final vertex.
Example 2.10
What is the language accepted by the automaton in Figure 2.9? It is easy to see
from the graph that the only way the nfa can stop in a final state is if the input is
either a repetition of the string 10 or the empty string. Therefore, the automaton
accepts the language L= {(10) n : n ≥0}.
What happens when this automaton is presented with the string w = 110?
After reading the prefix 11, the automaton finds itself in state q 2 , with the
transition δ (q 2 , 0) undefined. We call such a situation a dead configuration, and
we can visualize it as the automaton simply stopping without further action. But
we must always keep in mind that such visualizations are imprecise and carry
with them some danger of misinterpretation. What we can say precisely is that