CPSC 121: Models of ComputationAssignment #5, due Wednesday, November 27th, 2013 at 17:00[6] 1. Design a finite state machine that takes in a string of bits, and terminates in anaccepting state if the string of bits ends with 10110. Clearly indicate the meaningof each state. Hint: it can be done with 6 states; if you use more than 10 states,then you should rethink your approach.Solution : Here is
...[Show More]
CPSC 121: Models of Computation
Assignment #5, due Wednesday, November 27th, 2013 at 17:00
[6] 1. Design a finite state machine that takes in a string of bits, and terminates in an
accepting state if the string of bits ends with 10110. Clearly indicate the meaning
of each state. Hint: it can be done with 6 states; if you use more than 10 states,
then you should rethink your approach.
Solution : Here is a DFA that works. Each state is labeled by the sequence of
characters that would lead the DFA to it. For instance, the DFA is in the second
state from the left if the last characters it has seen are 001, 111 or 0011.
[6] 2. Design a deterministic finite-state automaton (DFA) that accepts exactly the strings
over the alphabet fA; B; : : : ; Zg that contain at least one D, and where every occurrences of OO must be followed (not necessarily immediately) by a L. For instance, your
DFA should accept the string DO NOT FEED THE BEAR, GOOGLE DOCS ARE USEFUL
and ROB FORD IS A VERY POOR SOCCER PLAYER but not the strings I LOVE CPSC,
CHEATING IS NOT GOOD, or POODLES EAT LOTS OF FOOD. Clearly indicate the meaning of each state.
Solution : Here is a DFA that works. As with the previous question, each state is
labeled with what it means for the DFA to be in this state.
[Show Less]
-preview.jpeg)
-preview.jpeg)
-preview.jpeg)
