(a) the set of bit strings that begin with two 0s
(b) the set of bit strings that contain two consecutive 0s
(c) the set of bit strings that do not contain two consecutive 0s
(d) the set of bit strings that end with two 0s
(e) the set of bit strings that contain at least two 0s
Solution: (a) Our goal is to construct a deterministic finite-state automaton that recognizes
the set of bit strings that begin with two 0s. Besides the start state s0, we include a
nonfinal state s1; we move to s1 from s0 if the first bit is a 0. Next, we add a final state s2, which
we move to from s1 if the second bit is a 0. When we have reached s2 we know that the first two
input bits are both 0s, so we stay in the state s2 no matter what the succeeding bits (if any) are.
We move to a nonfinal state s3 from s0 if the first bit is a 1 and from s1 if the second bit is a 1.
The reader should verify that the finite-state automaton in Figure 3(a) recognizes the set of bit
strings that begin with two 0s.
(b) Our goal is to construct a deterministic finite-state automaton that recognizes the set ofbit strings that contain two consecutive 0s. Besides the start state s0, we include a nonfinal
state s1, which tells us that the last input bit seen is a 0, but either the bit before it was a 1, or
this bit was the initial bit of the string.We include a final state s2 that we move to from s1 when
the next input bit after a 0 is also a 0. If a 1 follows a 0 in the string (before we encounter two
consecutive 0s), we return to s0 and begin looking for consecutive 0s all over again. The reader
should verify that the finite-state automaton in Figure 3(b) recognizes the set of bit strings that
contain two consecutive 0s.
(c) Our goal is to construct a deterministic finite-state automaton that recognizes the set of
bit strings that do not contain two consecutive 0s. Besides the start state s0, which should
be a final state, we include a final state s1, which we move to from s0 when 0 is the first
input bit. When an input bit is a 1, we return to, or stay in, state s0. We add a state s2, which
we move to from s1 when the input bit is a 0. Reaching s2 tells us that we have seen two
consecutive 0s as input bits. We stay in state s2 once we have reached it; this state is not final.
The reader should verify that the finite-state automaton in Figure 3(c) recognizes the set of bit
strings that do not contain two consecutive 0s. [The astute reader will notice the relationship
between the finite-state automaton constructed here and the one constructed in part (b). See
Exercise 39.]
(d) Our goal is to construct a deterministic finite-state automaton that recognizes the set of bit
strings that end with two 0s. Besides the start state s0, we include a nonfinal state s1, which
we move to if the first bit is 0. We include a final state s2, which we move to from s1 if the
next input bit after a 0 is also a 0. If an input of 0 follows a previous 0, we stay in state s2
because the last two input bits are still 0s. Once we are in state s2, an input bit of 1 sends us back
to s0, and we begin looking for consecutive 0s all over again. We also return to s0 if the next
input is a 1 when we are in state s1. The reader should verify that the finite-state automaton in
Figure 3(d) recognizes the set of bit strings that end with two 0s.
(e) Our goal is to construct a deterministic finite-state automaton that recognizes the set of bit
strings that contain two 0s. Besides the start state, we include a state s1, which is not final; we
stay in s0 until an input bit is a 0 and we move to s1 when we encounter the first 0 bit in the input.
We add a final state s2, which we move to from s1 once we encounter a second 0 bit. Whenever
we encounter a 1 as input, we stay in the current state. Once we have reached s2, we remain
there. Here, s1 and s2 are used to tell us that we have already seen one or two 0s in the input
string so far, respectively. The reader should verify that the finite-state automaton in Figure 3(e)
recognizes the set of bit strings that contain two 0s.
Comments
Post a Comment