CSCI 338: Homework 2

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

• To earn points, your answers must be easily readable.
• You will earn 1 point per problem for a reasonable looking solution.
• One problem will be selected for careful grading. The rest of the 10 points will be allocated to this problem.
• Solutions to all problems will be posted.

Partners

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.

Submission

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.