Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for the Second Midterm Examination Spring 2007 April 12


The best way to study is to look at Study guides and tests of past semesters. If any topic on those study guides was not yet covered, it will not be on the exam. In addition:
  1. Review your homework assignments.
  2. Review the topics covered in the lectures.
  3. There will be true/false questions.
  4. There will be some definitions and fill-in-the-blank questions.
  5. I will definitely have a question involving parsers.
  6. You will need to state the Church-Turing thesis, and explain its importance.
  7. I will possibly ask you to explain how a Turing Machine can emulate some other machine. For example, how can a TM emulate a stack machine? A machine with two tapes? I would want answers with pictures.
  8. I may ask you to state the pumping lemma for context-free 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.
  9. I will expect you to know how to prove that a language can be enumerated in canonical form by a machine if and only if some TM accepts it.
  10. I will expect you to know the process by which a language is proved to be NP-complete, given that some other language is known to be NP-complete.
  11. Study guides and tests from Previous Semesters