Computer Science 456/656
Automata and Formal Languages

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

1. There will be true/false questions. Some of these may be on the exam. (Any question in this list not related to material covered so far will not be on the test.)
2. There will be some definitions and fill-in-the-blank questions. (Any question in this list not related to material covered so far will not be on the test.)
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, provided we cover that topic before the test.
6. There will be a few more questions.
7. In addition to reviewing the homework problems, work the following problems in your textbook in preparation for the examination:
   1. Exercise 1.5 on page 84.
   2. Exercise 1.12 on page 85.
   3. Exercise 1.16 on page 86. (Use any method, not necessarily the method given in the textbook.)
   4. Exercise 2.1 on page 119 of your textbook, provided that we cover that material before the test.
   5. Exercise 2.4 on page 120 of your textbook, provided that we cover that material before the test.
   Do not hand any of these problems in.