Computer Science 456/656
Automata and Formal Languages

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

1. There will be true/false questions.
2. There will be some definitions and fill-in-the-blank questions.
3. There will be a problem where you have to either prove that a grammar is ambiguous, or find an equivalent unambiguous grammar, or both.
4. There will be a problem which relates sytax to semantics, that is, grammars to meaning, for languages where strings have meaning.
5. There will be some elementary questions involving Turing machines and computability. (Very little, since we have covered so little.)
6. A question I always ask is, "What is the Church-Turing thesis, and why is it important?"
7. I will ask a question like this one involving parsers. Here is one solution, but don't look at it until you try to work it out on your own.