It is convenient to introduce the extended transition function δ* : Q × ∑* →
Q. The second argument of δ * is a string, rather than a single symbol, and its
value gives the state the automaton will be in after reading that string. For
example, if
δ(q 0 ,a) = q 1
and
δ(q 1 ,b) = q 2 ,
then
δ * (q 0 ,ab) = q 2 .
Formally, we can define δ * recursively by
for all q ∈ Q, w ∈ Σ * , a ∈ Σ. To see why this is appropriate, let us apply these
definitions to the simple case above. First, we use (2.2) to get
But
Substituting this into (2.3), we get
Q. The second argument of δ * is a string, rather than a single symbol, and its
value gives the state the automaton will be in after reading that string. For
example, if
δ(q 0 ,a) = q 1
and
δ(q 1 ,b) = q 2 ,
then
δ * (q 0 ,ab) = q 2 .
Formally, we can define δ * recursively by
for all q ∈ Q, w ∈ Σ * , a ∈ Σ. To see why this is appropriate, let us apply these
definitions to the simple case above. First, we use (2.2) to get
But
Substituting this into (2.3), we get