CSC 456/656 Assignment 1
Due date, September 3, 2002, 4:00 PM.
All assignments must be handwritten
(not typed or printed from a computer file)
in your own handwriting, on 8.5 by 11 inch paper. Write your name on
each sheet, and do not fold the pages or crimp the corners.
Turn the pages in to me or to the graduate assistant on the due date.
-
There are two ways of illustrating a DFA described in the textbook, as
a transition diagram or as
a transition table.
For example, Figures 2.4 and 2.5 on pages 48 and 49 illustrate the same DFA in
those two ways,
while Figures 2.6 and 2.7 on page 51 illustrate another DFA, also in those
same two ways.
Consider this transition table for a DFA which we call A.
-
What is the alphabet for A? What is the set of states for A? What is the
set of final states for A?
-
Draw the transition diagram for A.
-
Find 10 strings that A accepts. Find 10 stings over its alphabet
that A does not accept.
-
Can you describe the language of A in a few English words?
(Hint: the phrase "binary numeral" should appear in your answer.)
Back to
Course Page