Since there is a λ-edge between q 2 and q 0 , we have immediately that δ *
(q 2 ,λ)contains q 0 . Also, since any state can be reached from itself by making no
move, and consequently using no input symbol,δ * (q 2 ,λ)also contains q 2 .
Therefore,
Using as many λ-transitions as needed, you can also check that
The definition of δ * through labeled walks is somewhat informal, so it is
useful to look at it a little more closely. Definition 2.5 is proper, since between
any vertices v i and v j there is either a walk labeled w or there is not, indicating
that δ * is completely defined. What is perhaps a little harder to see is that this
definition can always be used to find δ * (q i , w).
In Section 1.1, we described an algorithm for finding all simple paths
between two vertices. We cannot use this algorithm directly since, as Example
2.9 shows, a labeled walk is not always a simple path. We can modify the simple
path algorithm, removing the restriction that no vertex or edge can be repeated.
The new algorithm will now generate successively all walks of length one,
length two, length three, and so on.
There is still a difficulty. Given a w, how long can a walk labeled w be? This
is not immediately obvious. In Example 2.9, the walk labeled a between q 1 and
q 2 has length four. The problem is caused by the λ-transitions, which lengthen
the walk but do not contribute to the label. The situation is saved by this
observation: If between two vertices v i and v j there is any walk labeled w, then
there must be some walk labeled w of length no more than Λ + (1 + Λ) |w|,
where Λ is the number of λ-edges in the graph. The argument for this is: While
λ-edges may be repeated, there is always a walk in which every repeated λ-edge
is separated by an edge labeled with a nonempty symbol. Otherwise, the walk
contains a cycle labeled λ, which can be replaced by a simple path without
changing the label of the walk. We leave a formal proof of this claim as an
(q 2 ,λ)contains q 0 . Also, since any state can be reached from itself by making no
move, and consequently using no input symbol,δ * (q 2 ,λ)also contains q 2 .
Therefore,
Using as many λ-transitions as needed, you can also check that
The definition of δ * through labeled walks is somewhat informal, so it is
useful to look at it a little more closely. Definition 2.5 is proper, since between
any vertices v i and v j there is either a walk labeled w or there is not, indicating
that δ * is completely defined. What is perhaps a little harder to see is that this
definition can always be used to find δ * (q i , w).
In Section 1.1, we described an algorithm for finding all simple paths
between two vertices. We cannot use this algorithm directly since, as Example
2.9 shows, a labeled walk is not always a simple path. We can modify the simple
path algorithm, removing the restriction that no vertex or edge can be repeated.
The new algorithm will now generate successively all walks of length one,
length two, length three, and so on.
There is still a difficulty. Given a w, how long can a walk labeled w be? This
is not immediately obvious. In Example 2.9, the walk labeled a between q 1 and
q 2 has length four. The problem is caused by the λ-transitions, which lengthen
the walk but do not contribute to the label. The situation is saved by this
observation: If between two vertices v i and v j there is any walk labeled w, then
there must be some walk labeled w of length no more than Λ + (1 + Λ) |w|,
where Λ is the number of λ-edges in the graph. The argument for this is: While
λ-edges may be repeated, there is always a walk in which every repeated λ-edge
is separated by an edge labeled with a nonempty symbol. Otherwise, the walk
contains a cycle labeled λ, which can be replaced by a simple path without
changing the label of the walk. We leave a formal proof of this claim as an