Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for Final Examination

Finished

  1. There will be true/false questions. Some of these will be on the final exam.
  2. There will be one question involving construction or minimization of finite automata.
  3. There may be a question involving regular expressions.
  4. There will be some definitions and fill-in-the-blank questions.
  5. There will be a question involving constructing a CF grammar for a language.
  6. There will be a question requiring the use of the pumping lemma for context-free languages to prove that some particular language is not context-free.
  7. I will expect you to know what the universal language (also known as the halting problem) is, as well as the fact that it's undecidable, i.e., not recursive, and that it is recursively enumerable.
  8. I expect you to know what the Church Turing thesis is, and why it's important.
  9. At least one homework problem that was assigned during the semester will appear on the final.