FORMAL LANGUAGES AND COMPUTABILITY

The course studies the basics of formal language theory and computability. Formal languages have significant applications in compilers and automated text processing, while computability studies the intrinsic limitations of computers and algorithms.

The student will learn to master the theoretical concepts underlying the course and to solve exercises which prove their understanding. In particular, the student will learn the relationships between different computational models and their expressive power. The student will also learn to identify the most appropriate computational model to solve a given problem.

Specifically, the students will meet the following goals:

i) Knowledge and understanding: understanding of the basic concepts of the theory of formal languages ​​and computability.

ii) Ability to apply knowledge and understanding: ability to solve exercises related to the theoretical topics covered in the course.

iii) Judgment: ability to choose the most appropriate proof technique for a specific objective.

iv) Communication skills: knowing how to clearly and correctly explain the reasoning carried out in a mathematical proof.

v) Learning ability: knowing how to independently study new theoretical concepts from the world of formal languages ​​and calculability.

Basic knowledge of Discrete Mathematics

- Regular languages
- Context-free languages
- Turing machines
- Decidability
- Reductions
- Introduction to advanced topics

Michael Sipser - Introduction to the theory of computation, third edition

Written exam including exercises and theoretical questions. The exam will last 120 minutes and will propose 5 questions, whose goal is assessing the student's ability of solving problems related to the topics of the course and grasp the theoretical foundations of the material presented in the lectures. The written exam evaluates learning objectives from i) to v). During the exam it is forbidden the use of books, notes and electronic devices.

Lectures at the blackboard. Assignment of recommended exercises to solve.

Italian

The list of the presented topics will be regularly updated on Moodle.

written