CS 3800
W. Schnyder
Spring 2020
2/15/2020
Homework 6
(due Friday, February 21)
Instructions: This homework is to be submitted on GradeScope as a single pdf (not in parts) by
11:59 pm on the due date. You may either type your solutions in a word processor and print to
a pdf, or write them by hand and submit a scanned copy. Do write and submit your answers as
if they were a professional report. There will be point deductions if the submission isn’t neat (is
disordered, difficult to read, scanned upside down, etc. . . .).
Begin by reviewing your class notes, the slides, and the textbook. Then do the exercises below.
Show your work. An unjustified answer may receive little or no credit.
No late submission can be accepted as we wish to display solutions Saturday and complete the
grading before the exam.

L = w 2 f0; 1g∗ j w is a binary number divisible by 3
(We accept the empty string and strings that have leading zeros: ", 110 and 00110 all
belong to L.) Hint: Problem 11f in homework 2.
Solution: A DFA for L is
DFA41
carry 0 trap carry 1
[0 0 1]
[1 1 0]
[0 0 1][0 1 0][1 0 0][1 1 1] [0 0 0][0 1 1][1 0 1][1 1 0]
[0 0 0][0 1 1][1 0 1] [0 1 0][
q0
1 1
q2
0