CSCI 338: Homework 2

Sample Solution

Problems - This homework set is complete

  1. Problem 1.15 on page 85.
  2. The complement of set S is defined to be the set of all elements of the universe U that are not elements of S. Given DFA D1 = (Q1, Σ, δ1, q1, F1), show how to construct its complement D2 = (Q2, Σ, δ2, q2, F2) using a construction argument similar to those found on pages 59-63.
  3. Use the procedure described in Lemma 1.55 to convert the following regular expression to a nondeterministic finite automaton: (((00)*(11)) ∪ 01)
  4. Problem 1.20, parts (b) and (h) on page 86.
  5. Problem 1.21, part (a) on page 86.
  6. Show the DFA that recognizes any string that contains exactly two a's over Σ = {a, b} and then use the procedure described in Lemma 1.60 to convert it to a regular expression.

Grading - 10 Points


You may work alone or you may partner with one classmate. If you work with a partner, submit only one solution with both of your names on it.


Upload your submission to the D2L Dropbox for Homework 2 no later than 5:00 p.m. on Friday, February 5th. Late submissions receive no credit, but partial credit can be earned by making an ontime submission.

Valid XHTML 1.0!