Formal Languages, Computability, and Complexity

Lectures: Michel Abdalla ( & Pooya Farshim (
TA: Luise Jachiet (
Lectures: Thursdays 13:15-15:00 at Salle Henri Cartan
Classes: After each lecture from 15:15-17:00 (15 min break)
Mid-term: There will be a mid-term progress check on Nov 16.

The lectures by Pooya will be in English. You will have a choice of languages with Michel! The classes by Louis will be in French (unless you decide to switch). An outline of the course contents is given below. These more or less follow Sipser’s book. In early December, you need to decide on a presentation topic. A list of possible topics is given below. These will be updated and extended and you are welcome to suggest topics of your own choice.


Course Contents

  • Lecture 01 (28/09): Course outline. Deterministic and non-deterministic finite automaton. Equivalence of DFAs and NFAs. Closure properties.
  • Lecture 02 (28/09): Regular expressions and equivalence with DFAs/NFAs. The pumping lemma. Minimization of DFAs. 
  • Lecture 03 (05/10): Context-free grammars. Pushdown automaton. Equivalence of CGFs and PDAs. Parse trees and ambiguity. 
  • Lecture 04 (12/10): Pumping lemma for CFLs. Ogden’s Lemma. Closure properties of CFLs.
  • Lecture 05 (19/10): Turing machines. Equivalence of single and multi-tape TMs. Non-deterministic TMs. Diagonalization and the Halting Problem.
  • Lecture 06 (26/10): Reductions. Examples of (un)decidable languages. Decision properties of regular and context-free languages. 
  • Lecture 07 (02/11): Rice’s theorem. The Post correspondence problem. 
  • Lecture 08 (09/11): The recursion theorem. Undecidability of logical theories.
  • Lecture 09 (16/11): Kolmogorov complexity. Mid-term. 
  • Lecture 10 (23/11): Time Complexity: P, NP, and coNP. Extended Church-Turing Thesis. NP-completeness.
  • Lecture 11 (30/12): NP-completeness of SAT. Other complete problems.
  • Lecture 12 (07/12): Space complexity. Savitch’s Theorem. PSPACE-completeness. Classes L and NL, co-NL. NL=coNL.
  • Lecture 13 (14/12): Circuit complexity: class P/poly and NC. Existence of hard functions. Karp-Lipton. Meyer’s Theorem. P-Completeness.
  • Lecture 14 (04/01): Randomized algorithms: Schwartz-Zippel and primality. Classes BPP, RP, coRP, and ZPP. Error reduction and BPP in P/poly.
  • Lecture 15 (11/01): Cryptography. One-way functions and one-way permutations. Pseudorandom generators. The Goldreich-Levin Theorem.

Presentation Topics

  1. Repetition-Free Sequences
  2. Theorems of Lyndon–Schützenberger
  3. Moore and Mealy Machines
  4. DFA Minimization Algorithms 
  5. Deterministic Context-Free Languages 
  6. Context-Sensitive Languages
  7. Parikh’s Theorem
  8. The CYK Algorithm
  9. Cellular Automaton
  10. Recursive Functions
  11. Lambda Calculus
  12. Oracle Turing Machines & Arithmetic Hierarchy
  13. Undecidability of the Generalized 3+ 1 Problem
  14. The Unexpected Examination Paradox
  15. Ladner’s Theorem
  16. Complexity of Decision versus Search
  17. The Polynomial Hierarchy
  18. Barrington’s Theorem
  19. #P
  21. Parity Is Not in AC0
  22. Communication Complexity
  23. Average-Case Complexity
  24. The PCP Theorem 
  25. PAC Learning
  26. Relativization and Natural Proofs Barrier
  27. Hardness Amplification for OWFs
  28. Pseudorandom Functions
  29. Zero-Knowledge Protocols
  30. Quantum Computation

Previous year’s web-page.