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 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.
- 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.