-
EXAMPLE 6 Construct deterministic finite-state automata that recognize each of these languages.
(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 of
bit 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

Popular posts from this blog

psychology two questions n their answer

-
1) Describes the cognitive development of adolescence and its educational implication . Piaget's (1936) theory of cognitive development explains how a child constructs a mental model of the world. He disagreed with the idea that intelligence was a fixed trait, and regarded cognitive development as a process which occurs due to biological maturation and interaction with the environment. Piaget proposed four stages of cognitive development which reflect the increasing sophistication of children's thought: 1. Sensorimotor stage (birth to age 2) 2. Pre-operational stage (from age 2 to age 7) 3. Concrete operational stage (from age 7 to age 11) 4. Formal operational stage (age 11+ - adolescence and adulthood). Adolescence is a transitional stage of physical and psychological development that generally occurs during the period from puberty to legal adulthood (age of majority).Adolescence is usually associated with the teenage years but its physical, psychological or cultural e...
Read more

thread

-
Image
www.studtonight.com/operating-system What are Threads? Thread is an execution unit which consists of its own program counter, a stack, and a set of registers. Threads are also known as Lightweight processes. Threads are popular way to improve application through parallelism. The CPU switches rapidly back and forth among the threads giving illusion that the threads are running in parallel. As each thread has its own independent resource for process execution, multpile processes can be executed parallely by increasing number of threads. Types of Thread There are two types of threads : User Threads Kernel Threads User threads , are above the kernel and without kernel support. These are the threads that application programmers use in their programs. Kernel threads are supported within the kernel of the OS itself. All modern OSs support kernel level threads, allowing the kernel to perform multiple simultaneous tasks and/or to service multiple kernel system calls simultaneou...
Read more