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 formal language theory, 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 test with exercises, questions and proofs related to the main topics of the course. During the written test, the use of notes, books and electronic instruments is not permitted.

The written exam evaluates learning objectives from i) to v). In particular, the student will be assessed based on the following criteria:

i) Knowledge and understanding: The student must demonstrate familiarity with the formal notation introduced during the course, the main definitions, and the specific terminology.

ii) Ability to apply knowledge and understanding: The student must demonstrate the ability to solve exercises on the topics covered in the course.

iii) Judgment skills: The student must demonstrate the ability to apply the main proof techniques and adapt existing proofs.

iv) Communication skills: The student must demonstrate familiarity with the specific language and strong command of logical reasoning.

v) Learning ability: The student must demonstrate the capacity to understand concepts and definitions presented during the exam.

Regarding the indicated criteria, scores in the range of 18-22 indicate sufficient but limited skills, scores in the range of 23-26 indicate fair to more than fair skills, and scores in the range of 27-30 indicate good to excellent skills.

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

Italian

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

written