Example 2.3
Find a deterministic finite accepter that recognizes the set of all strings on Σ=
{a,b} starting with the prefix ab.
The only issue here is the first two symbols in the string; after they have
been read, no further decisions are needed. Still, the automaton has to process
the whole string before its decision is made. We can therefore solve the problem
with an automaton that has four states; an initial state, two states for recognizing
ab ending in a final trap state, and one nonfinal trap state. If the first symbol is
an a and the second is a b, the automaton goes to the final trap state, where it
will stay since the rest of the input does not matter. On the other hand, if the first
symbol is not an a or the second one is not a b, the automaton enters the nonfinal
trap state. The simple solution is shown in Figure 2.4.
Figure 2.4
Example 2.4
Find a deterministic finite accepter that recognizes the set of all strings on Σ=
{a,b} starting with the prefix ab.
The only issue here is the first two symbols in the string; after they have
been read, no further decisions are needed. Still, the automaton has to process
the whole string before its decision is made. We can therefore solve the problem
with an automaton that has four states; an initial state, two states for recognizing
ab ending in a final trap state, and one nonfinal trap state. If the first symbol is
an a and the second is a b, the automaton goes to the final trap state, where it
will stay since the rest of the input does not matter. On the other hand, if the first
symbol is not an a or the second one is not a b, the automaton enters the nonfinal
trap state. The simple solution is shown in Figure 2.4.
Figure 2.4
Example 2.4