# CSCI 338: Homework 2

## Problems - This homework set is complete

- Problem 1.15 on page 85.
- 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 D_{1} = (Q_{1}, Σ, δ_{1},
q_{1}, F_{1}), show how to construct its complement
D_{2} = (Q_{2}, Σ, δ_{2},
q_{2}, F_{2}) using a construction argument similar to
those found on pages 59-63.
- Use the procedure described in Lemma 1.55 to convert the following regular
expression to a nondeterministic finite automaton:
(((00)
^{*}(11)) ∪ 01)
- Problem 1.20, parts (b) and (h) on page 86.
- Problem 1.21, part (a) on page 86.
- 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.