CSE 105 Assignment 1
Due date, July 7, 2003, 8:00 AM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
-
Work Exercise 1.3 on page 84 of your textbook.
-
In Exercise 1.4, for each part, write down the minimum number of
states the DFA accepting the language has, and state whether one of
these must be the dead state.
(For example, (b) requires 4 states none of which is dead,
and (i) requires 3 states, one of which must be the dead state.)
Actually draw the state diagrams for (d) and (f).
-
Let S be the set of all integers of the form 3n+1, 4n+1, 5n+1, or 7n+1,
where n is a natural number.
(For example, 1, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 16, 17, 19 and 21 are in S,
but 2, 3, and 12 are not.)
Let L be the set of unary numerals for members of S.
-
Explain why there is an NFA with 20 states which accepts L. (You do not
have to draw it if your explanation is otherwise clear.)
-
Explain why no DFA with fewer than 420 states can accept L.
(Do not draw it!)
Hint.
-
Work Excercise 1.12 (b) on page 85 of your textook. Your answer must
be a minimal DFA. You may omit the dead state from
your state diagram.
-
Work Excercise 1.10 (b) on page 85 of your textbook.
-
Work Excercise 1.14 (a) on page 86 of your textbook.
-
Work Excercise 1.15 on page 86 of your textbook, but do not turn it in.
-
Work Excercise 1.16 on page 86 of your textbook, but do not turn it in.
-
A real-life computer could be emulated by a finite state transducer.
(See page 87 of your textbook.) Estimate the
number of states needed for a FST which emulates the PC you have at home
(or your friend's home, if you don't have one).
I really want an informal discussion, rather than a precise number.
Back to
Course Page