Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for the First Midterm Examination Spring 2004

1. There will be true/false questions. Some of these may be on the exam.
2. There will be some definitions and fill-in-the-blank questions.
3. There will be a question where you are required to construct the unique minimal DFA equivalent to a given NFA. You must show steps, and I will give you lots of blank space to work it.
4. There will be at least one question involving regular expressions.
5. There will be a question involving constructing a CF grammar for a language.
6. There will be a few more questions.
7. Work the following problems in your textbook in preparation for the examination:
   Exercise 1.1 on page 83.
   1. Exercise 1.5 on page 84.
   2. Exercise 1.12 on page 85.
   3. Exercise 1.16 on page 86. (But use any method, not necessarily the method given in the textbook.)
   4. Exercise 2.1 on page 119 of your textbook.
   5. Exercise 2.4 on page 120 of your textbook.
   Do not hand any of these problems in.
8. The test is very easy. I should be able to finish it in ten minutes, fifteen at the most.