Cod: 21078
Department: DCET
Scientific area: Computer Engineering
Total working hours: 156
Total contact time: 26

The relationship between formal languages and computing is the subject of this curricular unit. The various formalisms of representation of languages are addressed, to the concept that originated from the current computer: the Turing machine. The notions of resolveability, handling and computational complexity are closely related to this concept.

1. Regular languages
2. Context-independent languages
3. Turing machines
4. Resolveability and Handling

Upon completion of this learning unit, the student should be able to:
Understanding and applying the various types of formal languages
Establishing relations between algorithms/problems and their formal representation in terms of the Turing machine.

Regular expression and languages.
Context-free grammars and languages.
Turing machines.
Decidability and treatability.

Hopcroft & Ullman. Introduction to Automata and Language Theory. Addison-Wesley.
Valença & Barros. Fundamentos da Computação, Vol. I & II. Universidade Aberta.


Continuous assessment is privileged: 2 or 3 digital written documents (e-folios) during the semester (40%) and a presence-based final exam (p-folio) in the end of the semester (60%). In due time, students can alternatively choose to perform one final presence-based exam (100%).