4 lecture hours
2 exercise hours

6  ECTS credits

### Abstract

•  The theory of computation comprises the mathematical underpinnings of computer science. It introduces three major topics: formal languages and automata theory, computability theory, and complexity theory. This course focuses on the first two, and provides an introduction to the third. Complexity theory classifies problems with respect to their intrinsic degree of hardness, or the amount of computational resources (in terms of space and time) required to solve them. Computability theory addresses a more fundamental issue: is a given problem solvable (by a computer) in the first place? The theory of formal languages and automata investigates mathematical models of computation, and classifies them with respect to their computational power. These models are used to answer questions and prove results in both computability and complexity theory. In addition to its foundational role, the theory of computation had had vast applications in various areas of computing. These include the specification of the syntax of programming languages, compiler construction, string processing, and cryptography.

### Outline

•  This course introduces students to three areas of theoretical computer science: formal languages, computability theory, and complexity theory.

1. Formal languages: regular and context-free languages; context-sensitive languages(context-sensitive grammars and linear-bounded automata); type-0 languages (unrestrictedgrammars and Turing machines); the Chomsky hierarchy.
2. Computability theory: recursive and recursively enumerable languages; Turingcomputable functions; decidable and undecidable problems; Church's thesis.
3. Complexity theory: time and space complexity of Turing machines; the complexity classes P and NP; reducibility, NP-hardness and NP-completeness; examples of NP-complete problems.

### Objectives

•  After passing this course, students should be able to do the following:

• Determine the membership of a given string in an intensionally defined formal language.
• Prove properties of an intensionally defined formal language.
• Precisely describe the language of a given finite automaton.
• Design finite automata to recognize a given regular language.
• Transform a nondeterministic FA into a deterministic FA.
• Describe regular languages using regular expressions
• Transform a regular expression into the equivalent FA.
• Transform a FA into the equivalent regular expression.
• Prove properties of regular languages.
• Determine whether a given language is not regular, using the pumping lemma for regular languages.
• Precisely describe the language generated by a given context-free grammar.
• Design CFGs to generate a given context-free language.
• Transform a CFG into a CFG in Chomsky normal form.
• Precisely describe the language of a given pushdown automaton.
• Design a PDA to recognize a given CFL.
• Transform a CFG into the equivalent PDA.
• Transform a PDA into the equivalent CFG.
• Prove properties of CFLs.
• Determine whether a given language is not context-free, using the pumping lemma for CFLs.
• Design Turing machines to decide, compute, or enumerate given languages.
• Prove whether a given language is undecidable.
• Prove whether a given language is Turing-unrecognizable.
• Describe the behavior of functions using the O and o notation.
• Determine the time complexity of a Turing machine program.
• Prove that a given language is in P.
• Prove that a given language is in NP.
• Prove that a given language is NP-complete.

### Goals

•  By the end of this course, students will develop the rigor and skills required to precisely present and prove various properties of computations. Students will be able to precisely state and prove properties of various formal languages and models of computation. They will also be capable of giving sound arguments for why a given problem is, or is not, (computationally) solvable. If a problem is solvable, students will be able to precisely establish whether possible solutions are feasible.

### Course Editions  