For years, I’ve been meaning to write a new theoretical computer science textbook to replace the ones I’ve used in my classes, that never seem to address the things students struggle with. Unfortunately, I’ve never had the time.
Rather than wait any longer, I’ve decided to start writing out the book a few pages at a time and posting it here, by sections; feedback is appreciated! Each section is tagged with the name of the chapter it belongs to.
Table of Contents: (in progress)
- How to Read This Book
- Mathematical Preliminaries
- Languages Have Class!
- Regular Languages (with problem set)
- Closure Properties of Regular Languages
- Regular Expressions and Regular Grammars
- Pumping Lemmas
- The Pumping Lemma for Regular Languages
- Context-Free Languages
- Closure Properties of Context-Free Languages
- Context-Free Grammars
- The Pumping Lemma for Context-Free Languages
- Context-Sensitive Languages
- Turing Machines
- Recursive and Recursively Enumerable Languages
- The Halting Problem