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 consecutive ’E’s occu
...
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 consecutive ’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]
