The final exam will be held on Monday July 30 at 12:30-3:00 pm in PAC 9, 10.
The final exam is closed-book (i.e. no aids will be permitted). The final exam will cover everything in the course with emphasis on the second half of the course (Lectures 13-23). You may use any result that we have proved in class or on the assignments.
You should have a good grasp of the definitions of each language class and their representations and you should understand the properties of each language class and their representations (closure properties, determinism vs nondeterminism, ambiguity, hardness, completeness, etc.). Generally, you can expect the kinds of questions to be asked to be similar in flavour to the assignment questions, although they will not be as involved.
There are two flavours of question. The first is true/false; here, you'll be asked to determine whether or not a statement is true or false, with no proof necessary. The second are the usual problems that you've seen on assignments.
You will not be asked to perform any lengthy algorithms (subset construction, Chomsky normal form, etc.) although you should know what they are supposed to show. You will not be expected to explicitly list every part of a machine/grammar when asked to present a construction. You will not be asked to formally show via induction that a machine/grammar accepts/generates a language, although you should be able to generally explain why it's true. However, you will be expected to write a pumping lemma proof properly. As on the assignments, you will not be asked to formally construct a Turing machine, but only to describe its operation.
Regarding some parts of complexity theory, there won't be any deeply involved questions on things that you haven't seen on assignments, like the time hierarchy theorem and the assortment of esoteric results, nor will there be much on space complexity and the polynomial hierarchy. These kinds of things can make great True/False questions though.