Syllabus

The following is a more detailed and up-to-date version of the UPC syllabus of the course.

1. Introduction
   1. Basic mathematical notions
      • sets and tuples
      • relations and functions
   2. Formal languages
      • strings and languages
      • concatenation
      • Kleene star
      • homomorphisms
   3. Common proof techniques
      • proofs by contradiction
      • proofs by cases
      • proofs by induction
      • Pigeonhole principle
   4. Cantor Diagonalization
      • almost all languages do not have a finite description
        
2. Regular languages
   1. Deterministinc Finite Automata (DFA)
   2. Equivalent models
      • Non-deterministic Finite Automata (NFA) and \lambda-NFAs
      • regular expressions (regex)
      • equivalence between DFA/NFA/\lambda-NFA/regex
      • Arden’s Lemma
   3. Minimization of DFAs (Moore’s algorithm)
   4. Closure properties of regular languages w.r.t.
      • union, intersection, and complement
      • concatenation and Kleene star
      • reverse
      • homomorphism and inverse of homomorphism
   5. Proofs of non-regularity
      • \{a^nb^n \mid n\in \mathbb N\} is not regular
      • pumping lemma for regular languages
      • distinguishing extensions
3. Context-free languages
   1. Context-free grammars (CFGs)
   2. Parsing trees and ambiguity
   3. Depuration of CFGs and Chomsky Normal Form
   4. CYK algorithm
   5. Closure properties of context-free languages w.r.t.
      • union, concatenation, and Kleene star
      • reverse
      • homomorphism
      • intersection with a regular language
   6. Push-down automata (PDAs)
      • equivalence with CFGs
      • deterministic PDAs
      • uniquely-accepting PDAs
   7. Pumping lemma for context-free languages
      • \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free
4. Decidable and semidecidable languages
   1. Deterministic (1-tape) Turing Machines (DTM)
      • language recognized and function computed by a DTM
   2. Equivalent models
      • nondeterministic Turing Machines
      • TMs with multiple tapes
   3. Church-Turing Thesis
   4. Gödel numbering of TMs
   5. Universal Turing Machine
   6. \mathbf{R}/\mathbf{RE}/\mathbf{coRE}
      • projection theorem
      • \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}
      • closure properties of \mathbf{R}/\mathbf{RE}/\mathbf{coRE}
      • \mathbf{RE}\neq \mathbf{R}
   7. Many-one reductions
   8. Rice’s Theorem
   9. Natural problems not in \mathbf{R}
5. Elements of complexity theory
   1. \mathbf{P}/\mathbf{NP}/\mathbf{coNP}/\mathbf{EXP}
   2. \mathbf{NP}-completeness
      • \mathtt{SAT} and Cook-Levin’s Theorem
      • polynomial-time reductions
   3. Time hierarchy theorem and \mathbf{P}\neq \mathbf{EXP}