Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for the Second Midterm Examination Fall 2006 October 31


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. 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.
  10. Study guides and tests from Previous Semesters