Computer Science 456/656
Automata and Formal Languages

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

Note Changes October 27.

  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.) One question I might ask is to sketch the proof that every multitape TM can be emulated by a single tape TM.
  6. A question I always ask is, "What is the Church-Turing thesis, and why is it important?"
  7. I will definitely repeat the question of finding a minimal DFA equivalent to a given NFA-epsilon. Here is an example in postscript format and the same in in pdf format.
  8. I will ask some very elementary question involving parsers, as I described in class Tuesday, October 27.