Find a dfa that accepts all the strings on {0,1}, except those containing the
substring 001.
In deciding whether the substring 001 has occurred, we need to know not
only the current input symbol, but we also need to remember whether or not it
has been preceded by one or two 0’s. We can keep track of this by putting the
automaton into specific states and labeling them accordingly. Like variable
names in a programming language, state names are arbitrary and can be chosen
for mnemonic reasons. For example, the state in which two 0’s were the
immediately preceding symbols can be labeled simply 00.
If the string starts with 001, then it must be rejected. This implies that there
must be a path labeled 001 from the initial state to a nonfinal state. For
convenience, this nonfinal state is labeled 001. This state must be a trap state,
because later symbols do not matter. All other states are accepting states.
This gives us the basic structure of the solution, but we still must add
provisions for the substring 001 occurring in the middle of the input. We must
define Q and δ so that whatever we need to make the correct decision is
remembered by the automaton. In this case, when a symbol is read, we need to
know some part of the string to the left, for example, whether or not the two
previous symbols were 00. If we label the states with the relevant symbols, it is
very easy to see what the transitions must be. For example,
δ(00, 0) = 00
because this situation arises only if there are three consecutive 0’s. We are only
interested in the last two, a fact we remember by keeping the dfa in the state 00.
A complete solution is shown in Figure 2.5. We see from this example how
useful mnemonic labels on the states are for keeping track of things. Trace a few
strings, such as 100100 and 1010100, to see that the solution is indeed correct.
Figure 2.5
substring 001.
In deciding whether the substring 001 has occurred, we need to know not
only the current input symbol, but we also need to remember whether or not it
has been preceded by one or two 0’s. We can keep track of this by putting the
automaton into specific states and labeling them accordingly. Like variable
names in a programming language, state names are arbitrary and can be chosen
for mnemonic reasons. For example, the state in which two 0’s were the
immediately preceding symbols can be labeled simply 00.
If the string starts with 001, then it must be rejected. This implies that there
must be a path labeled 001 from the initial state to a nonfinal state. For
convenience, this nonfinal state is labeled 001. This state must be a trap state,
because later symbols do not matter. All other states are accepting states.
This gives us the basic structure of the solution, but we still must add
provisions for the substring 001 occurring in the middle of the input. We must
define Q and δ so that whatever we need to make the correct decision is
remembered by the automaton. In this case, when a symbol is read, we need to
know some part of the string to the left, for example, whether or not the two
previous symbols were 00. If we label the states with the relevant symbols, it is
very easy to see what the transitions must be. For example,
δ(00, 0) = 00
because this situation arises only if there are three consecutive 0’s. We are only
interested in the last two, a fact we remember by keeping the dfa in the state 00.
A complete solution is shown in Figure 2.5. We see from this example how
useful mnemonic labels on the states are for keeping track of things. Trace a few
strings, such as 100100 and 1010100, to see that the solution is indeed correct.
Figure 2.5