FORMAL LANGUAGES AND COMPUTABILITY

Academic year
2021/2022 Syllabus of previous years
Official course title
CALCOLABILITA' E LINGUAGGI FORMALI
Course code
CT0374 (AF:306351 AR:172452)
Modality
On campus classes
ECTS credits
6
Degree level
Bachelor's Degree Programme
Educational sector code
INF/01
Period
1st Semester
Course year
3
Where
VENEZIA
Moodle
Go to Moodle page
The course studies the basics of formal language theory and computability. Formal languages have significant applications in compilers, 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.
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. During the exam it is forbidden the use of books, notes and electronic devices.
Lectures at the blackboard
Italian
The list of the presented topics will be regularly updated on Moodle.
written
Definitive programme.
Last update of the programme: 02/07/2021