Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for the Final Examination Spring 2004

  1. The final examination will be comprehensive, but will be weighted toward material that has been covered in class since the last examination.
  2. Study homework questions and prior exams.
  3. Study old examinations in the course, but if a topic was not covered in lectures this semester, it will not be on the final examination. Don't forget that the textbook is different than from any prior UNLV semester, although it is the same as the textbook I used at UCSD in the Summer of 2003.
  4. There will be true/false questions.
  5. There will be some definitions and fill-in-the-blank questions.
  6. There will be a proof.
  7. Sections of the textbook to review:
    1. All of Chapter 0 (Introduction), even though I didn't cover all of it in class. It should have been covered in the prerequisite courses, except for the subsection on "Strings and Languages." Most of that chapter is just "brushing up" on the tools you need for the rest of the material.
    2. All of Chapter 1.
    3. All of Chapter 2, except that I did not cover the rather difficult proofs in section 2.2.
    4. Sections 3.1 and 3.2
    5. All of Chapter 4.
    6. Reducibility (but not all of Chapter 5.)
    7. Sections 7.2, 7.3, and most of Section 7.4. The Cook-Levin Theorem. (I gave you that theorem in class, but did not give you its name.)