Theory of Computation

Recommended Prerequisites

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

Teaching Methods

In the Theoretical classes, expository methods will be used relating to the fundamental concepts of the different contents covered in the curricular unit, which will then be tested in an exercise format in the Theoretical Practical and Laboratory Practices class.

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

Continuos Assessment
Frequency: 100.0%

Final Assessment
Exam: 100.0%

Bibliography

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

Theory of Computation: Making Connections, Jim Hefferon, Independently published, 2023.

Theory of Computation Simplified: Simulate Real world Computing Machines and Problems with Strong Principles of Computation, Varsha H. Patil, Vaishali S. Pawar, Swati A. Bhavsar, Aboli H. Patil, BPB Publications, 2023.

Algorithms and Theory of Computation Handbook, Mikhail J. Atallah, Marina Blanton, Chapman and Hall/CRC, 2022.

Introduction th the Theory of Computation, Michael Sipser, 3rd Ed., PWS Publishing Co, 2021.