CSE 350 - Textbook and Topics
Textbook
- Michael Sipser,
Introduction to the Theory of Computation.
Second edition, Thomson Course Technology, 2006
(ISBN 978-0-534-95097-2).
Topics
Regular Languages [Chapter 1]
- Finite automata [1.1]
- Nondeterminism [1.2]
- Regular expressions [1.3]
- Nonregular languages [1.4]
Context-free Languages [Chapter 2]
- Context-free grammars [2.1]
- Pushdown automata [2.2]
- Non-context-free languages [2.3]
The Church-Turing Thesis [Chapter 3]
- Turing Machines [3.1]
- Variants of Turing Machines [3.2]
- The Definition of Algorithm [3.3]
Decidability [Chapter 4]
- Decidable Languages [4.1]
- The Halting Problem [4.2]
Reducibility [Chapter 5]
- Undecidable problems [5.1, 5.2]