all strings consisting of an arbitrary number of a's, followed by a single b. All
other input strings are rejected. In set notation, the language accepted by the
automaton is
L = {a n b:n≥0}.
Figure 2.2
These examples show how convenient transition graphs are for working with
finite automata. While it is possible to base all arguments strictly on the
properties of the transition function and its extension through (2.1) and (2.2), the
results are hard to follow. In our discussion, we use graphs, which are more
intuitive, as far as possible. To do so, we must, of course, have some assurance
that we are not misled by the representation and that arguments based on graphs
are as valid as those that use the formal properties of δ. The following
preliminary result gives us this assurance.
Theorem 2.1
Let M =(Q,Σ,δ,q 0 ,F) be a deterministic finite accepter, and let G M be its
associated transition graph. Then for every q i , q j ∈ Q, and w ∈ Σ + , δ * (q i ,w) = q j
if and only if there is in G M a walk with label w from q i to q j .
Proof: This claim is fairly obvious from an examination of such simple cases as
Example 2.1. It can be proved rigorously using an induction on the length of w.
Assume that the claim is true for all strings v with |v|≤ n. Consider then any w of
length n + 1 and write it as
w = va
Suppose now that δ * (q i ,v) = q k . Since |v|=n, there must be a walk in G M labeled v
from q i to q k . But if δ * (q i ,w) = q j , then M must have a transition δ (q k ,a) = q j , so
other input strings are rejected. In set notation, the language accepted by the
automaton is
L = {a n b:n≥0}.
Figure 2.2
These examples show how convenient transition graphs are for working with
finite automata. While it is possible to base all arguments strictly on the
properties of the transition function and its extension through (2.1) and (2.2), the
results are hard to follow. In our discussion, we use graphs, which are more
intuitive, as far as possible. To do so, we must, of course, have some assurance
that we are not misled by the representation and that arguments based on graphs
are as valid as those that use the formal properties of δ. The following
preliminary result gives us this assurance.
Theorem 2.1
Let M =(Q,Σ,δ,q 0 ,F) be a deterministic finite accepter, and let G M be its
associated transition graph. Then for every q i , q j ∈ Q, and w ∈ Σ + , δ * (q i ,w) = q j
if and only if there is in G M a walk with label w from q i to q j .
Proof: This claim is fairly obvious from an examination of such simple cases as
Example 2.1. It can be proved rigorously using an induction on the length of w.
Assume that the claim is true for all strings v with |v|≤ n. Consider then any w of
length n + 1 and write it as
w = va
Suppose now that δ * (q i ,v) = q k . Since |v|=n, there must be a walk in G M labeled v
from q i to q k . But if δ * (q i ,w) = q j , then M must have a transition δ (q k ,a) = q j , so