Review on Languages, Automata and Grammars: regular expressions, Linear Grammars and Context Free Grammars.
Review: NFSA with epsilon moves and DFSA. Properties of Regular languages.
Review: Regular expressions and FSA. Pumping Lemma.
PDA. Equivalence between PDA and CFG. Examples.
Parse Trees. Leftmost derivations. Ambiguity. Chomsky Normal form. Statement of the Pumping Lemma for CFL.
Proof of the Pumping Lemma for CFL's. Exercises.
Building the Chomsky Normal Form: elimination of epsilon productions and unit productions in a CFG. Preparation to the midterm examination.
Midterm 1.
Review of the midterm examination. Languages and decision problems. Countable and uncountable sets. Cantor's theorem.
Turing Machines. Instantaneous descriptions. Recursively enumerable languages.
Multitape Turing machines. Turing Machines and digital computers. Nondeterministic Turing machines.
Nondeterministic vs deterministic Turing machines. 1-1 codification of strings of binary digits into integers. Arithmetization of Turing machines.
Enumerations of Turing machines. Languages and Decision Problems. Definition of Recursive sets and Recursively Enumerable sets. Formulation of the halting problem.
Church's Thesis. Universal Turing machines. Undecidability of the Halting problem.
Problems Reductions. Closure properties of Recursive and Recursively enumerable sets. Equivalent definitions of Recursively Enumerable sets.
Examples of reductions. Recursion Theorem. Rice's Theorem.
Midterm 2.
The classes P and NP. Examples of problems in P: Minimum Spanning Tree. Kruskal's algorithm. Examples of problems in NP: Satisfiability. Polynomial time reductions. NP-completeness.
Proof of Cook's Theorem.