Theory of Computation

Recommended Prerequisites

Logic, discerte structures, algebra, mathematical analysis, computer programmimg; English.

Teaching Methods

Theoretical classes  (2h weekly) for presentation and discussion of the materials of the successive chapters, with computational demonstrations when appropriate. Examples are also solved in the blackboard.

Theoretical-practical classes (1h weekly) for problem solving from a sheet of problems delivered to the students each week.

Practical Laboratorial classes (2h weekly) for additional support in problem solving and for the resolution of thematic challenges.

Learning Outcomes

To study the several models of automata (finite, stack, Turing Machine) and formal grammars (regular, context free and context sensitive, and recursive) and the relations among them, showing its relations with the programming languages and compilers. These are structuring knowledge of the informatics as a scientific discipline that develop the mental capability to follow the present and future evolution of informatics and computation. Also the several computation models, developed in the past, are addressed and compared. The notion of complexity associated with the Turing-computability is introduced, to show the present limits of computation.

Competencies in analysis and synthesis, written communication, informatics knowledge relative to the study focus, problem solving, critical thinking, autonomous learning, practical application of theoretical knowledge, creativity.

Work Placement(s)

No

Syllabus

Chap.1. Introduction and basic definitions; languages, grammars, automata.

Chap.2. Finite automata, deterministic, nondeterministic and their relations.

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

Chap.4. Properties of regular languages, the pumping lemma.

Chap.5. Context-free languages, parsing.

Chap.6 Simplification of grammars, normal forms.

Chap.7. Stack automata, non-deterministic and deterministic..

Chap.8. Properties of context-free languages, pumping lemmas.

Chap.9. Turing Machine, Turing hypothesis.

Chap.10.Other Turing Machine models, linearly bounded automata..

Chap.11 Hierarchies of formal languages and automata..

Chap.12. The limits of algorithmic computation.

Chap.13. Other models of computation (recursive functions, Post, rewriting, lambda-Calculus)

Chap.14. An introduction to the theory of complexity,  problems P e NP.

Head Lecturer(s)

António Dourado Pereira Correia

Assessment Methods

Assessment
2 Tests: 40.0%
Exam: 60.0%

Bibliography

An Introduction to Formal Languages and Automata, Peter Linz, 3rd Ed., Jones and Bartelett Computer Science, 2001.

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 the Theory of Computation, Michael Sipser, PWS Publishing Co, 1997.