Readings for CS 3800

• 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)
• Section 7.1 (Measuring Complexity)
• Section 7.2 (The Class P)
• Section 7.3 (The Class NP)
• Section 7.4 (NP-completeness)

• Undecidability of the Halting Problem

• Section 6.2 (Decidability of Logical Theories)

Slide 8 (tensor product) is incorrect. The elements of the first column vector should be x₀ and x₁, the elements of the second should be y₀ and y₁, and the elements of the third should be z₀ and z₁.