Syllabus and References

The course includes significant mathematical content. Students are expected to have prior experience with writing mathematical proofs and a general level of mathematical maturity. For those who meet these criteria and are curious about the theoretical limits of computation, the course promises to be both intellectually stimulating and enjoyable.

Syllabus

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

Tip0. 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, cases, induction, Pigeonhole principle

References:
(Sipser 2013, \S 0) (Cases and Màrquez 2003, \S 1)
(Hopcroft et al. 2007, \S 1)

Note1. Regular languages
  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 et al. 2007, \S 2.1 - 2.5, \S 3.1-3.2 and \S 4.1-4.4)

Caution2. Context-free languages
  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 et al. 2007, \S 5.1, \S 5.4, \S 7.1-7.3)

Warning3. Decidable and semidecidable languages
  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. Cantor Diagonalization
    almost all languages do not have a finite description
  4. \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 et al. 2007, \S 8-9.3)
(Kozen 1997, Lectures 28-32)

Important4. Elements of complexity theory
  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 et al. 2007, \S 10)

References

Books

The main book we will follow for the course is (Sipser 2013).

Sipser, Michael (2013).
Introduction to the Theory of Computation. 3rd edition.
Cengage Learning.
Available at UPC library

Books in Catalan covering the topics of the course are (Cases and Màrquez 2003) and (Serna et al. 2004).

Cases, Rafel, and Lluís Màrquez (2003).
Llenguatges, Gramàtiques i Autòmats : Curs Bàsic. 2a ed.
Edicions UPC.
Available at UPC library

Serna, Maria José, Carme Àlvarez, Rafel Cases, and Antoni Lozano (2004).
Els Límits de La Computació : Indecidibilitat i NP-Completesa. 2a ed.
Edicions UPC.
Available at UPC library

Other books covering the topics of the course (with more details than (Sipser 2013)) are (Hopcroft et al. 2007) and (Kozen 1997).

Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman (2007).
Introduction to Automata Theory, Languages, and Computation. 3rd edition.
Pearson Addison Wesley.
Available at UPC library

Kozen, Dexter (1997).
Automata and Computability.
Undergraduate Texts in Computer Science. Springer.
Available at UPC library

Videos

In this course, we cover the material in M. Sipser’s MIT video lectures up to lecture 16 more or less (although on some topics we dig more in detail than Sipser’s lectures).

In Catalan/Spanish there are also available G. Godoy’s video lectures.