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 language representation are discussed, up to the concept that gave rise to the current computer: the Turing machine. The notions of decidability, tractability, and computational complexity are closely related to this concept.

1. Regular languages2. Context-free languages3. Turing Machines4. Decidability and tractability

Upon completion of this curricular unit, the student should be able to:- Understand and apply the several types of formal languages.- Establish relationships between algorithms/problems and their formal representation in terms of a Turing machine.

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


Hopcroft, Motwani & Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition. Addison-Wesley. ISBN 0-321-47617-4


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