Readings for CS 3800
Required readings
- Read in textbook:
- Chapter 0 (Introduction)
- Section 1.1 (Finite Automata)
- Section 1.2 (Nondeterminism)
- Section 1.3 (Regular Expressions)
- Section 1.4 (Nonregular Languages)
- Section 2.1 (Context-Free Grammars)
- Section 2.2 (Pushdown Automata)
- Section 2.3 (Non-Context-Free Languages)
- Section 3.1 (Turing Machines)
- Section 3.2 (Variants of Turing Machines)
- Section 3.3 (The Definition of Algorithm)
- Section 4.1 (Decidable Languages)
- Section 4.2 (Undecidability)
- Section 5.1 (Undecidable Problems From Language Theory)
- Read on the World-Wide Web:
- Read in textbook:
- Section 6.2 (Decidability of Logical Theories)
- Section 7.1 (Measuring Complexity)
- Section 7.2 (The Class P)
- Section 7.3 (The Class NP)
- Section 7.4 (NP-completeness)
Optional Readings
Last updated 12 April 2016.
Click here to validate HTML on this page.