Languages and Computation
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.
Hopcroft, Motwani & Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition. Addison-Wesley. ISBN 0-321-47617-4
E-learning.
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%).