Part 9 Theoretical Computer Science
Textbooks
- Michael Sipser, Introduction to the Theory of Computation (Any Edition).
- Peter Linz, An Introduction to Formal Languages and Automata, 5th Edition.
- Dexter C. Kozen, Automata and Computability.
Formal Language Theory
Topics | Subtopics | Sipser | Linz | Kozen |
---|---|---|---|---|
Introductory Material | Why Formal Languages; Sets, Alphabets, Languages | Sec 0.2 | Sec 1.2 | Chapter 1 |
Finite Automata | Basic Definitions; Deterministic FA; Nondeterministic FA; Epsilon-Transition | Sec 1.1, 1.2 | Sec 2.1; Sec 2.1; Sec 2.2 | Chapter 3; Chapter 5 |
Regular Languages | Regular Expressions; From Reg. exp. to FA | Sec 1.3 | Sec 3.1; Sec 3.2 | Chapter 9 |
Context-Free Languages | Context-Free Grammars; Derivations, Parsing, Trees Regular Grammars; Chomsky Normal Form | Sec 2.1 | Sec 5.1; Sec 5.1; Sec 3.3; Sec 6.2 | Chapter19; Chapter 21 |
Push-Down Automata | From CFG to PDA | Sec 2.2 | Sec 7.2 | Chapter 24 |
Computability Theory
Topics | Subtopics | Sipser | Linz | Kozen |
---|---|---|---|---|
Turing Machines | Basic Definitions; Variations of TM; Church Turing Thesis | Chapter 3 | Sec 9.1; Chapter 10; Sec 9.3 | Chapter 28, 29, 30 |
Decidability | Decidable Problems; The Halting Problem | Chapter 4 | Chapter 12 |
Complexity Theory
Topics | Subtopics | Sipser | Linz | Kozen |
---|---|---|---|---|
Time Complexity | Measuring Complexity; The Class P; The Class NP; NP-Completeness; Additional NP-complete Prbs | Sec 7.1; Sec 7.2; Sec 7.3; Sec 7.4; Sec 7.5 | Chapter 14 | |
Space Complexity | The class PSPASE | Sec 8.2 |