LAP6

In this course students will study the theoretical foundations of computer science, i.e., the theory ofcomputation. The course has two parts:

i) Automata Theory. Abstract models called automata are at the core of all computers. This part of the course provides a close examination of automata, formal languages and grammars, and classifies them according to the Chomsky Hierarchy.
ii) Computability and Complexity Theory. This part of thecourse examines what kinds of problems can be solved using algorithms (computability) and, in the case of computable problems, how inherently difficult they are to solve(complexity).

Theme 1:Mathematical concepts and basic formal reasoning. Sets, relations, functions, character strings, and languages. Demonstrations.
Theme 2: Regularlanguages: Finite automata, regular grammars, regularexpressions, and the applications of these. How to provethat a language is not regular.
Theme 3:Context-free languages: push-down automata, context-freegrammars, and the applications of these.
Theme 4: Recursivelanguagesand recursively enumerable languages: Turingmachines and unrestricted grammars.
Theme 5: Turing machines, deterministic and non-deterministic.
Theme 6:Computable languages. Diagonalization and reduction for proving the non-computability of a language.
Theme 7:Recursively enumerable languages. Relationship with computable languages. Rice’s Theorem.
Theme 8:Complexity theory. The classes P and NP. The study of NP-complete problems.