Theory of Computation

Recommended Prerequisites

Logic, discrete mathematics, algebra, mathematical analysis, programming, English.

Teaching Methods

2h per week of theoretical lectures, 1h per week to study examples in anfiteatre (case-studies) and 2h per week for  problem solving in practical-laboratorial classes with small groups.

Learning Outcomes

To study the different types of automata (finite automata, pushdown automata, Turing Machines) and of formal grammars (regular, context-free, context dependent, recursives) and the relations among them, as well as its relations with programming languages and computers.These are struturing concepts in informatics as a scientific discipline and they develop tha mental capability to follow the present and future developments of informatics and computation. The several computation models developed in the past are also comparativelly addressed. The theory of complexity is introduced around the Turing-computability framework, to show the present limitations of computation.

Moreover, the course develops the analysis and synthesis capabilities, written communication, problem solving, critical thinking, autonumous learning, practical application of theoretical concepts, criativity.

Work Placement(s)

No

Syllabus

1. Introduction and basic definitions: languages, grammars, automata.

2. Finite automata, deterministic and non deterministic and their relations. Transducers.

3. Regular languages, regular grammars, regular expressions, finite automata and their relations.

4. Properties of regular languages, the pumping lema.

5. Context-free languages (non regular), parsing.

6. Simplification of context-free grammars and canonical forms.

7. Pushdown automata non-deterministic and deterministic.

8- Properties of context free languages (closeness, pumping lemas).

9- Turing Machines, the Turing thesis.

10-Other models of Turing Machines.

11- Hierarchies of formal languages and automata.

12-The limits of algorithmic computation.

13- Other models of computation (recursive functions, Post, rewritting systems, lambda calculus).

14. An introduction to the theory oc complexity, P and NP problems.

Head Lecturer(s)

Pedro Manuel Henriques da Cunha Abreu

Assessment Methods

Assessment
Frequency: 100.0%

Final Assessment
Exam: 100.0%

Bibliography

An Introduction to Formal Languages and Automata, Peter Linz, 5th Ed., Jones and Bartlett Learing, 2012

Models of Computation and Formal Languages, R. Gregory Taylor, Oxford University Press, 1998.

Introduction to Automata Theory, Languages and Computation, 2nd   Ed., John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Addison Wesley, 2001.

Elements for the Theory of Computation, Harry Lewis and Christos Papadimitriou, 2nd Ed., Prentice Hall, 1998.

Introduction th the Theory of Computation, Michael Sipser, PWS Publishing Co, 1997.

Sítios web diversos a indicar nas aulas