Below is a selection of excercises and problems from the textbook you can use to prepare for the final. If you think it is too long, don't worry, the actual final will be definitely shorter than that, but this selection of problems should give you a pretty good idea of the coverage. We will not provide written solutions to these problems before the final. If you have questions, please come to office hour and/or discussion.
Topics: DFAs; NFAs; Regular expressions; Equivalence of DFA, NFA and RE; Closure properties of regular languages; Pumping lemma for regular languages.
Reading: whole chapter
Practice Problems 1, 4, 10, 12, 14, 23
Topics: CFGs; PDA; Equivalence of CFG and PDA; Closure properties of context free languages; Pumping lemma for context free languages
Reading: whole chapter, excluding Chomsky Normal Form
Practice Problems 1, 2, 6, 15
Topics: Turing machines; variants of turing machines
Reading: whole chapter
Practice Problems 7, 8, 10
Topics: Decidable problems concerning regular and context free languages; Undecidable problems; Unrecognizable problems
Reading: whole chapter
Practice Problems 1, 3, 11
Topics: Reducibility; mapping redugibility; proving undecidable and unrecognizable problems by reduction
Reading: sections 5.1 and 5.3.
Practice Problems 4, 5, 7, 10, 12