Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for the Second Midterm Examination Spring 2006 April 6


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. There will be true/false questions.
  3. There will be some definitions and fill-in-the-blank questions.
  4. I will try to think of some question involving parsers, but it will be difficult for me to come up with one that can be worked in 5 minutes.
  5. Look at a diagram of a Turing machine and say what it does, such as, "It shifts its input string one space to the right," or, "It deletes all zeros and compresses the rest of the string."
  6. Prove that any language accepted by any NTM is accepted by some TM. You will need to use the Church-Turing thesis.
  7. Something involving unrestricted grammars.
  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