Formal Languages and Automata Theory
198:452 & 198:508
Fall, 2022
Here is a brief summary of what was covered each day, along with an
indication of what I plan to cover in the next lecture.
- Sept. 6: Administrivia, overview, start of Regular Sets and Finite
Automata (Most of Chapter 1.1.). Closure of regular sets under complementation,
union, and intersection.
- Sept. 8:
Nondeterministic Finite Automata, NFAs can be smaller than DFAs.
DFAs and NFAs have equalivalent expressive power. Closure of regular sets under
concatenation and *.
- Sept. 13: Intro to Regular Expressions, Regular expressions and DFAs have
equivalent expressive power (building a regular expression, given any DFA). (Guest Lecture)
- Sept. 15: More with regular expressions. Non-regular sets; the Pumping Lemma.
(Guest Lecture)
- Sept. 20: More practice with the Pumping Lemma.
Example of a non-regular set that satisfies the Pumping Lemma.
The Myhill-Nerode Theorem. How to minimize a DFA.
- Sept. 22: Start of Chapter 2; Context-Free Grammars, derivations, parse trees,
Ambiguity, Chomsky Normal Form, closure of the CFLs under union and *
- Sept. 27:
the CYK Parsing Algorithm.
Pushdown Automata. Closure of CFLs under intersection with a regular set. (See problem 2.18.)
- Sept. 29: Pushdown Automata are equivalent to CFGs. The Pumping Lemma for CFLs.
- Oct. 4: Proof of the Pumping Lemma for CFLs. Non-closure properties of the CFLs.
Brief introduction to computability theory and Turing machines.
- Oct. 6: Introduction to decidable and Turing-acceptable languages. Turing machines.
A set is decidable if and only if both it and its
complement are Turing-acceptable. Undecidability of A_TM. Enumerators.
The Church-Turing Thesis. Countable and Uncountable sets; Diagonalization.
Nondeterministic Turing machines (Chapters 3 and 4).
- Oct. 11: Midterm Examination (in class).
- Oct. 13: More on Diagonalization, Countability and Computability.
Decidable problems from automata theory (Chapters 3 and 4). Reducibility and
completeness (Chapter 5).
- Oct. 18:
Examples of m-reductions. The Post Correspondence Problem.
(Guest Lecture)
- Oct. 20: Undecidability of the Post Correspondence Problem;
Undecidable problems about context-free languages.
- Oct. 25: (Un)Decidability of Logical theories
(Chapter 6). (Students who want more details about how to show
that Th(N,+,*) is undecidable may want to consult this source:
https://www.cs.rutgers.edu/~allender/509/incompleteness.pdf )
Rice's Theorem.
- Oct. 27: More on (Un)Decidability of Logical theories. Provability and independence.
(Chapter 6) Start of Complexity Theory: The complexity classes P and NP; polynomial-time
reducibility, NP-complete problems. 3-SAT reduces to CLIQUE. (Chapter 7)
- Nov. 1: Review of homework and m-reducdtions.
The Cook-Levin Theorem: SAT is NP-complete.
- Nov. 3: SAT reduces to Hamiltonian Path (Chapter 7)
Space Complexity; Relations among DTIME, NTIME, DSPACE, and
NSPACE; Savitch's Theorem; ALL_NFA is in PSPACE; logspace reducibility is closed under
composition, PATH is in NL (Chapter 8)
- Nov. 8: PATH is NL-complete. Examples of problems in PSPACE, PSPACE-complete problems, NL=coNL (Chapter 8)
- Nov. 10: Space and Time Hierarchy Theorems, Intractable Problems; REX^ is in EXPSPACE (Chapter 9)
- Nov. 15: REX^ is complete for EXPSPACE; Oracles, An oracle relative to which P is not equal
to NP (Chapter 9)
- Nov. 17: Circuit Complexity (Chapter 9) P is in P/poly; P= logspace-uniform poly-size.
CVP is complete for P. Circuit-SAT is NP-complete, and an alternate proof of Cook's Theorem.
Probabilistic computation, BPP, RP, and ZPP (Chapter 10)
Polynomial Identity Testing is in coRP.
- Nov. 22: The Schwartz-Zippel Lemma (to finish showing that PIT is in coRP).
BPP is in P/poly. EXPSPACE is not in P/poly.
- Nov. 29: Introduction to Alternation and the Polynomial Hierarchy (Chapter 10).
- Dec. 1: Interactive Proofs (Section 10.4) The final
will be made available after the lecture.
- Dec. 6: Cryptography (Section 10.6). Kolmogorov complexity (Section 6.4)
- Dec. 8: More on Kolmogorov complexity: The set of Kolmogorov-random strings has no infinite
Turing-acceptable subset. Time-bounded Kolmogorov complexity, and an optimal algorithm
to find satisfying assignments. The Recursion Theorem (Section 6.1) and applications
to logic. Here are some notes
on how to use the Recursion theorem to construct an explicit example of a formula that is
true but not provable in Peano Arithmetic (assuming that PA is consistent).
- Dec. 13: More on Kolmogorov complexity.
- Dec. 16: The final will be due at noon.