Topics of the Theory of Computation
Code
9648
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Matemática
Credits
6.0
Teacher in charge
Vitor Hugo Bento Dias Fernandes
Weekly hours
4
Total hours
56
Teaching language
Português
Objectives
The goal of this course is to study several classes of formal languages (in particular the Chomsky hierarchy: regular, context-free, context-sensitive, recursively enumerable languages) and the finite structures that generate or recognize them (grammars and machines).
Prerequisites
-
Subject matter
1. Rational and recognizable languages: automata, languages, transition monoids, syntactic monoids and congruences, minimal automata, Kleene''''''''''''''''s theorem.
2. The Chomsky hierarchy: regular languages, context-free languages, grammars, Pushdown automata, Turing Machines.
3. Decidability problems.
Bibliography
1. M. Sipser, "Introduction to the Theory of Computation", Thomson, 2006.
2. J.E. Hopcroft e J.D. Ullman, “Introduction to Automata Theory, Languages and Computation”, Addison Wesley, 1979.
3. D.C. Kozen, “Automata and Computability”, Springer, 1997.
4. M. Delgado, "Teoria Algébrica dos Autómatos, FCUP, 2001
5. J.E. Pin, “Varieties of Formal Languages”, Plenum, New-York, 1986.
Teaching method
Classes consist of oral explanation of the theory and of solving problems.
If the number of students is less than 5, classes will be tutorial. The student prepares the contents of each chapter using the specific bibliography indicated and solves related problems.
Evaluation method
Continuous evaluation: 3 sets of problems to solve (40%+40%+20%). students may be required to make an oral presentation (with discussion) of their solutions.