Computer Science 456/656
Automata and Formal Languages

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

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 may be a question where you are required to minimize a DFA.
4. There may be a question where you are required to find a DFA equivalent to a given NFA. This question could be combined with the previous one.
5. There may be one or more questions involving regular expressions.
6. There may be a question involving constructing a CF grammar for a language.
7. There may be questions related to parse trees, derivations, or ambiguity.
8. There will be a question were you must fill in the table for the CYK algorithm, as we did in class.
9. I may ask you to state the pumping lemma for regular languages. If you write down all the words, but in the wrong order, you might get no partial credit, because the order of the words in the definition is critical.
10. There may be a question that is very hard, that most students will not be able to answer, in order to challenge the top students.
11. Here are some more exercises to work in preparation:
12. Exercise 1.7 on page 84 of your textbook.
    This was Exercise 1.5 on page 84 of the first edition.
13. Exercise 1.16 on page 86.
    This was Exercise 1.12 on page 85 of the first edition.
    
14. Exercise 1.21 on page 86. (Use any method, not necessarily the method given in the textbook.)
    This was Exercise 1.16 on page 86 of the first edition.
15. Exercise 2.1 on page 128 of your textbook.
    This was Exercise 2.1 on page 119 of the first edition.
16. Exercise 2.4 on page 128 of your textbook.
    This was Exercise 2.4 on page 120 of the first edition.