University of British Columbia - CPSC 121assignment 5 solutions Models of Computation

Document Content and Description Below

CPSC 121: Models of Computation Assignment #5, due Tuesday, April 5th, 2016 at 17:00 [7] 1. Design a deterministic finite-state automaton (DFA) that takes in a string of bits, and terminates in an ... accepting state exactly when the string of bits contains the substring 1011. Clearly indicate the meaning of each state. Hint: it can be done with 5 states; if you use more than 10 states, then you should rethink your approach. Solution : Here is a DFA that works. The DFA is in state i (starting with i = 0, from left to right) if the last i bit the DFA read are the first i bits of 1011. So for instance, the DFA is in state 3 if the last three bits it read were ’101’. [7] 2. Design a deterministic finite-state automaton (DFA) that accepts exactly the strings over the alphabet fA; B; : : : ; Zg that contain at least one A, where every occurrence of D must be followed (not necessarily immediately) by a E, and where every occurrence of H must be followed (not necessarily immediately) by a I. For instance, your DFA should accept the strings • OCTAL • ADHESIVE • HILARIOUS • HEXADECIMAL but not the strings • ADRIAN • MANACLED • MULTIPLEXER • DODECAHEDRON Clearly indicate the meaning of each state (hint: our solution uses eight of them) [Show More]

Last updated: 1 year ago

Preview 1 out of 10 pages