Again, the transition function can be extended so its second argument is a
string. We require of the extended transition function δ * that if then Q j is the set
of all possible states the automaton may be in, having started in state q i and
having read w. A recursive definition of δ * , analogous to (2.1) and (2.2), is
possible, but not particularly enlightening. A more easily appreciated definition
can be made through transition graphs.
Definition 2.5
For an nfa, the extended transition function is defined so that δ * (q i ,w) contains
q j if and only if there is a walk in the transition graph from q i to q j labeled w.
This holds for all q i , q j ∈ Q, and w ∈ Σ * .
Example 2.9
Figure 2.10 represents an nfa. It has several λ-transitions and some undefined
transitions such as δ(q 2 ,a).
Suppose we want to find δ * (q 1 ,a) and δ * (q 2 ,λ). There is a walk labeled a
involving two λ-transitions from q 1 to itself. By using some of the λ-edges twice,
we see that there are also walks involving λ-transitions to q 0 and q 2 .
Thus,
δ * (q 1 ,a) = {q 0 ,q 1 ,q 2 }.
Figure 2.10