Computer Science > STUDY GUIDE > University of British Columbia - CPSC 121assignment sol5(1) Models of Computation (All)

University of British Columbia - CPSC 121assignment sol5(1) Models of Computation

Document Content and Description Below

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 More]

Last updated: 2 years ago

Preview 1 out of 10 pages

Buy Now

Instant download

We Accept: