Fall 2018

*Note: this syllabus is subject to
change*

**1. Finite Automata and Regular Languages (7 lectures)**

*Sipser** - chapter 1*

Sets, characters, alphabets, strings, languages

definitions and proofs, recursion and induction

regular expressions (REs), regular languages (RLs)

deterministic and nondeterministic Finite Automata

theorems: equivalence of descriptive power for REs/DFAs/NFAs

closure properties of RLs

pumping lemma for RLs(algorithms for equivalence and minimization of DFAs)

(the LEX tool)

**2. Pushdown Automata and Context-Free Languages (6 lectures)**

*Sipser** - chapter 2*

context-free grammars (CFGs), context-free languages (CFLs)

derivations: leftmost, rightmost, parse trees

ambiguity

closure properties of CFLs

RLs as a subset of CFLs (two ways to prove it)

Deterministic CFLs

push-down automata (PDAs): regular/string-pushing/simple

Chomsky normal form

theorems: equivalence of PDAs and CFGs

relation between string derivation (leftmost) and parsing (PDA computation)

pumping lemma for CFLs(intersection of RLs and CFLs)

(CYK parsing)

(BNF grammars)

(the YACC tool)

**3. Turing Machines (4 lectures)**

*Sipser** - chapter 3*

Turing Machines: ordinary / nondeterministic / multitape

Equivalence of various TM extensions

Deciding vs. recognizing vs. enumerating

Encoding/specification of a TM/PDA/FSA

Simulating other machines, Universal Turing Machine

Church-Turing thesis

(Algorithmic vs. interactive computation)

**4. Decidability/Recognizability of
problems ****(5 lectures)**

*Sipser** - chapters 4-5*

Decidability of A

_{X}, E_{X}, EQ_{X}problems

(Diagonalization)

Undecidability of the halting problem

Reducing between problems

Undecidability of tiling problems, Post systems

(Rice's theorem)

**4. Complexity Theory (4 lectures)**

*Sipser** - chapter 7*

Measuring complexity

The classes P and NP

Certificates vs. nondeterminism

NP-complete problems