Syllabus

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

  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, cases, induction, Pigeonhole principle
  4. Cantor Diagonalization
    almost all languages do not have a finite description

References:
(Sipser 2013, \S 0 and \S 4.2 The diagonalization method (pp. 202 until the end of Theorem 4.17)
(Cases and Màrquez 2003, \S 1)
(Hopcroft, Motwani, and Ullman 2007, \S 1)

  1. Deterministic Finite Automata (DFA) and equivalent models
    Non-deterministic Finite Automata (NFA) and \lambda-NFAs, regular expressions (regex), equivalence between DFA/NFA/\lambda-NFA/regex, Arden’s Lemma.
  2. Minimization of DFAs (Moore’s algorithm)
  3. Closure properties of regular languages
    union, intersection, complement, concatenation and Kleene star, reverso, homomorphism and inverse of homomorphism
  4. Proofs of non-regularity
    \{a^nb^n \mid n\in \mathbb N\} is not regular, pumping lemma for regular languages, distinguishing extensions

References:
(Sipser 2013, \S 1.1-1.4)
(Cases and Màrquez 2003, \S 4-6.4 and \S 7.1)
(Hopcroft, Motwani, and Ullman 2007, \S 2.1 - 2.5, \S 3.1-3.2 and \S 4.1-4.4)

  1. Context-free grammars (CFGs)
    Parsing trees and ambiguity. Depuration of CFGs and Chomsky Normal Form
  2. CYK algorithm
  3. Closure properties of context-free languages
    union, concatenation, and Kleene star, reverse, homomorphism, intersection with a regular language, inverse homomorphism
  4. Push-down automata (PDAs)
    equivalence with CFGs, deterministic PDAs, uniquely-accepting PDAs
  5. Proofs of non context-freeness
    Pumping lemma for context-free languages. \{a^nb^nc^n \mid n\in \mathbb N\} is not context-free. Proofs of non context-freeness by closure properties

References:
(Sipser 2013, \S 2.1-2.3)
(Cases and Màrquez 2003, \S 2-3 and \S 7.2-7.3)
(Hopcroft, Motwani, and Ullman 2007, \S 5.1, \S 5.4, \S 7.1-7.3)

  1. Turing Machines
    Deterministic (1-tape) Turing Machines (DTM), language recognized and function computed by a DTM, equivalent models (nondeterministic Turing Machines, TMs with multiple tapes). Church-Turing Thesis. Gödel numbering of TMs. Universal Turing Machine
  2. Decidable (\mathbf{R}), semi-decidable(\mathbf{RE}), and co-semi-decidable (\mathbf{coRE}) languages
    projection theorem, \mathbf{R}=\mathbf{RE}\cap \mathbf{coRE}, closure properties of \mathbf{R}/\mathbf{RE}/\mathbf{coRE}, a glimpse into the arithmetical hierarchy
  3. \mathbf{RE}\neq \mathbf{R}
    \mathtt {K, HALT,\dots}\notin \mathbf R, many-one reductions, natural problems not in \mathbf{R}

References:
(Sipser 2013, \S 3-5)
(Serna et al. 2004, \S 1-3)
(Hopcroft, Motwani, and Ullman 2007, \S 8-9.3)
(Kozen 1997, Lectures 28-32)

  1. \mathbf{P}/\mathbf{NP}/\mathbf{coNP}/\mathbf{EXP}
    \mathbf{NP}-completeness, \mathtt{SAT} and Cook-Levin’s Theorem, polynomial-time reductions, a glimpse into the polynomial hierarchy
  2. \mathbf{NP}-intermediate problems
    factoring, discrete log, graph isomorphism, Ladner’s theorem
  3. \mathbf{P}\neq \mathbf{EXP}
    time computable functions and time hierarchy theorem

References:
(Sipser 2013, \S 7 and \S 9.1-9.2)
(Hopcroft, Motwani, and Ullman 2007, \S 10)