University of British Columbia - CPSC 121Assignment 5 Sample Solution Models of Computation

Document Content and Description Below

CPSC 121: Models of Computation Assignment #5, due Tuesday April 7th, 2015 at 17:00 [6] 1. Design a DFA that accepts exactly the strings over the alphabet fA; B; : : : ; Zg in which every pair of c... onsecutive ’E’s occurs before every pair of consecutive ’O’s. For instance, your DFA should accept the strings \FOOD FOR THOUGHT", \DO NOT FEED THE PIGEONS", \I LOVE CPSC" and \THIS BEEF IS GOOD TOO" but not \LOOK AT THE SHEEP". Clearly indicate the meaning of each state. Solution : Here is a DFA that works. In order to proceed to the third state, this DFA will need to see a string that ends with \OO", and does not contain any earlier instances of \OO". Once it has seen \OO", seeing two consecutive ’E’s sends the DFA into the rightmost non-accepting state, from which it can never leave. [6] 2. 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 1010. 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. 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 either \001" or \11".[7] 3. Write regular expressions describing the following sets of strings: [3] a. Binary strings that contains the substring 01 but not the substring 011. Hints: • You may use the HTML file from lab 8 to test your regular expressions. • How would you write a regular expression that matches strings that do not contain the substring 011? • My answer is 16 characters long, including the beginning- and end-ofstring markers. Solution : The idea is the following: consider the first occurrence of the substring 01. This 0 could be preceded by a number of other 0’s; these could themselves come after some 1’s. This gives us the initial part of the pattern: ^1*(0+1). After this initial copy of 01, we will need either the end of string, or another 0 (since we can’t have 011). After this (or these) 0’s, we can have another 1 again. Thus the pattern 0+1 will repeat. To deal with the case where the string ends with 01, with no 0 afterwards, we can make the last 1 optional. Hence we arrive at the following regular expression: ^1*(0+1)(0+1?)*$ [4] b. Strings over the alphabet fA; B; : : : ; Zg in which every pair of consecutive ’E’s occurs before every pair of consecutive ’O’s (see question 1). Solution : Such a string will contain an initial portion that can be anything at all except for two consecutive ’O’s. Then there will (optionally) be a pair of ’O’s, followed by anything as long as there are no two consecutive ’E’s. But how do we say a substring does not contain two copies of x in a row? We can do this by writing that every copy of x must be followed by something that is not x (unless it’s at the end of the substring, in which case it’s not followed by any character). We thus obtain the regular expression (the OO will match the first occurrence of the substring OO; there may be other copies of it later, of course): [Show More]

Last updated: 1 year ago

Preview 1 out of 10 pages