Computer Science 456/656
Automata and Formal Languages

CSC 456/656 Study Guide for the Final Examination Fall 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.
  4. There will be true/false questions. Two very likely true/false questions could be: "It is decidable whether a given string is in the language generated by a given context-free grammar," and "It is decidable whether two given context-free grammars generate the same language."
  5. There will be some definitions and fill-in-the-blank questions.
  6. There will be a proof. The proof I am most likely to give you is to use the pumping lemma for regular languages to prove that {anbn} is not regular.
  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 Chomsky Normal Form, nor the rather difficult proofs in section 2.2. (Nevertheless, you need to know the statements of those theorems.)
    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. Don't forget that the language called SAT in the book is essentially the same as the language I named Lsat in class. Similarly, I gave a different name for the language 3SAT in class.
    8. If, in any answer on the test, you use the textbook's notation or definition rather than what I gave in class, that is perfectly acceptable. It would be wise to make a note of that on your test paper.
  8. Consider the language L described by the regular expression (0+1)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1). Find the exact number of states of the minimal DFA that accepts L. (Do not attempt to draw it, since it has thousands of states.) Then draw the diagram of a much smaller NFA that accepts the same language.
  9. Give a specific example of a language which is not recursively enumerable, and show why it is not accepted by any TM.