# 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