Theory of computation

Theory of Computation

Instructor :emanuele Viola

Overview of class.
Slides .PDF, .ODP.


Math primer. Reading: Sipser Chapter 0. Think like the pros, sections 1,2, and 4.4.
Slides .PDF, .ODP. Regular languages and finite automata. Reading: Sipser Chapter 1.
Slides .PDF, .ODP.
DFAs ,regular operations
closure properties ,non-determinism, equivalence of NFAs and DFAs
regular expressions,equivalence of RE and FA, the pumping lemma
Context-free languages and pushdown automata. Reading: Sipser Chapter 2.
Slides .PDF, .ODP.
-context-free grammars
-ambiguity
-pushdown automata
-equivalence of CFLs and PDAs
-pumping lemma for CFLs
-closure properties
Turing Machines and Computability. Reading: Sipser Chapter 3, 4, 5, and Problem 5.28.
Slides .PDF, .ODP.
-Turing Machine variants
-Church-Turing thesis
-cardinality of infinite sets
-diagonalization
-undecidability
-Halting Problem
-reducibility
-Rice’s theorem
Complexity. Reading: Sipser Chapter 7.
Slides .PDF, .ODP.