Final Review Problems

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.

Chapter 1

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

Chapter 2

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

Chapter 3

Topics: Turing machines; variants of turing machines

Reading: whole chapter

Practice Problems 7, 8, 10

Chapter 4

Topics: Decidable problems concerning regular and context free languages; Undecidable problems; Unrecognizable problems

Reading: whole chapter

Practice Problems 1, 3, 11

Chapter 5

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