CSE 350 - Textbook and Topics
Textbook
- Michael Sipser,
Introduction to the Theory of Computation.
Third edition, Cengage Learning, 2013
(ISBN 978-1-13318779-X).
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]
- Undecidability [4.2]
Reducibility [Chapter 5]