COMP4141

Contents

Theory of Computation

  1. Formal Languages and Automata
    1. Regular Operations, Expressions and Languages
    2. Finite Automata
    3. Equivalence of Finite Automata and Regular Expressions
    4. Determinisation of Finite Automata
    5. Nerode's Congruence and Non-Regular Languages
    6. Context-Free Grammars and Languages
    7. Chomsky Normal Form
    8. Word Problem for Context-Free Grammars
    9. Derivation Trees
    10. Pumping Lemma and Non-Context-Free Languages
    11. Equivalence of Context-Free Grammars and Pushdown Automata
    12. Decidability Problems for Context-Free Languages
  2. Computability
    1. Words, Word Functions and Formal Languages
    2. Formal Problems
    3. Turing Machines, Computability, (Semi-)Decidability
    4. Universal Turing Machines
    5. Church-Turing Thesis
    6. Other Turing Machine Models
    7. Halting Problem
    8. Reductions and Undecidability Proofs
    9. Concrete Decidable and Undecidable Problems
  3. Complexity
    1. Running Times, Storage Location and Complexity Classes
    2. Complexity of certain Satifiabilty Problems
    3. Nondeterminism and NP
    4. Polynomial Reductions and NP-Completeness
    5. NP-Complete Problems
    6. Optimization Problems and Approximation
    7. Concrete Optimization Problems
    8. Randomization
    And, if time permits, one of