FORMAL LANGUAGES AND COMPUTABILITY

Academic year 2017/2018 Syllabus of previous years
Official course title CALCOLABILITA' E LINGUAGGI FORMALI
Course code CT0374 (AF:212597 AR:97047)
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
Course objectives
The course studies the basic of formal language theory and computability. The student will learn to master the theoretical concepts underlying these topics and to solve exercises which prove their understanding.
Pre-requirements
Discrete Mathematics
Contents
- Regular languages
- Context-free languages
- Turing machines
- Decidability
- Reductions
- Introduction to advanced topics
Referral texts
Michael Sipser - Introduction to the theory of computation, third edition
Type of exam
written
Assessment methods
Written exam including exercises and theoretical questions. The exam will last 150 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.
Teaching methods
Lectures
Teaching language
Italian
Sustainability
  • Course with sustainable contents
  • University credits of sustainability: 6
Last update of the programme
03/02/2018