Computability and Complexity/Introduction
This book is intended as a guide to the topics of computability and complexity in theoretical computer science for the mid-level undergraduate student. It assumes a working knowledge of discrete math, and uses Perl for all example programs.
The emphasis of the work so far has been on formal languages, particularly the Chomsky hierarchy, and on the machines that correspond to that hierarchy. The major areas that need filling out are the section on reducibility, and the sections on time and space complexity. Adding more language classes outside the Chomsky hierarchy would also improve the formal languages section, and adding information about the pumping lemmas to the sections on Regular Languages and the Context Free Languages would improve those sections.