CSC 456/656 Assignment 1
Due date: Thursday, January 29, 2004, 11:30 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.1 and 1.2 on on page 83 of your textbook, but do not
turn them in.
-
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).
-
Work Exercise 1.10 (b) on page 85 of your textbook. (This is very
easy, really, since you just have to give one simple counter-example.)
-
Work Exercise 1.12 (b) on page 85 of your textook. (It is not necessary
to use the exact construction given by Theorm 1.19: any method will do.)
Your answer must be a minimal DFA.
You may omit the dead state from your state diagram.
-
Try to work Exercise 1.14 on page 86 of your textbook, but
turn in only (b) this time. (You may have to turn in the others later.)
-
Work Exercise 1.15 on page 86 of your textbook, but
turn in only (e) this time. (You may have to turn in the others later.)
-
Work Exercise 1.16 on page 86 of your textbook, but do not turn it in
this time.
Back to
Course Page