
Course unit
AUTOMATA, LANGUAGES AND COMPUTATION
INP8084178, A.A. 2019/20
Information concerning the students who enrolled in A.Y. 2019/20
ECTS: details
Type 
ScientificDisciplinary Sector 
Credits allocated 
Educational activities in elective or integrative disciplines 
INF/01 
Computer Science 
2.0 
Core courses 
INGINF/05 
Data Processing Systems 
7.0 
Course unit organization
Period 
First semester 
Year 
1st Year 
Teaching method 
frontal 
Type of hours 
Credits 
Teaching hours 
Hours of Individual study 
Shifts 
Lecture 
9.0 
72 
153.0 
No turn 
Prerequisites:

In order to be able to successfully attend this class, a solid mathematical basis and a thorough knowledge of the concepts and methodologies underlying automatic data processing are necessary. More specifically, it is assumed that the student is familiar with the most common mathematical proof techniques, including proof by induction. It is also assumed general knowledge of computer programming, including recursive programming, and knowledge of the most common data structures such as trees and graphs. 
Target skills and knowledge:

The course has two main goals: (i) transferring knowledge about the most common models for formal representation of computation; (ii) acquiring the ability of abstract formalisation as applied to the analysis of a computation.
More specifically, the knowledge to be acquired is:
1. basic concepts of computational models, such as automata and grammars
2. basic concepts of computational resources, such as time and space
3. the concept of formal language as a mathematical representation of a problem
4. the concepts of computability, decidability and tractability of a problem
The skills that the student will develop during the course are:
1. to represent computation in an abstract way
2. to represent a problem through a formal language, and to study its mathematical properties 
Examination methods:

The verification of the acquired knowledge and the expected skills is carried out by means of a mandatory, written final test. During the test each student is asked to answer questions regarding the theoretical notions investigated during the class and to carry out the analysis of computational systems and formal languages. 
Assessment criteria:

The evaluation criteria used for the final examination in order to verify the acquired knowledge and skills are as follows
1. completeness of acquired knowledge
2. level of abstraction achieved in the analysis of computational systems and formal languages
3. use of proper terminology in written presentation
For the overall evaluation, the active participation in the technical discussions on the electronic forum during the course will also be considered, as well as the merits acquired in the solution of the contests proposed in the class. 
Course unit contents:

Basic techniques for mathematical proofs. Definition of basic concepts for formal languages. Characterisation of computational problems in terms of formal languages.
Deterministic finite automata, nondeterministic finite automata, and nondeterministic finite automata with epsilontransitions. Regular expressions and their relationship to finite state automata. Properties of regular languages.
Contextfree grammars and derived trees; simplification of contextfree grammars and canonical forms. Pushdown automata and their relationship to contextfree grammars. Properties of contextfree language.
Turing machines: basic definitions and construction techniques. Recursively enumerable (computable) languages/problems, and recursive (decidible) languages. ChurchTuring thesis. Proof of the existence of languages/functions that cannot be decided or computed. Intractable problems and the notion of NPcompleteness. Other classes of problems. 
Planned learning activities and teaching methods:

The class is delivered through frontal lessons using slides digitally distributed to students in advance. In order to facilitate discussion, collaboration, and selfevaluation of the learning process by students during the class,
an electronic forum supervised by the teacher is made available to students on the moodle platform, where they can discuss the resolution of theoretical problems and applicationoriented exercises proposed by the teacher. Finally, to encourage the active participation of students in the class and to motivate them to keep up with the different topics, small contests are proposed by the teacher, which are awarded with bonus tokens that are taken into account in the final evaluation. 
Additional notes about suggested reading:

Class topics are covered by the reference textbook. Additional teaching material is also provided through the moodle platform, in the form of slides and handouts with exercises. 
Textbooks (and optional supplementary readings) 

J.E. Hopcrpft, R.Motwani, J.D.Ullman, Automi, Linguaggi e CalcolabilitÃ . : Pearson, 2018. terza edizione

Innovative teaching methods: Teaching and learning strategies
 Lecturing
 Interactive lecturing
 Questioning
 Active quizzes for Concept Verification Tests and class discussions
 Loading of files and pages (web pages, Moodle, ...)
Innovative teaching methods: Software or applications used
 Moodle (files, quizzes, workshops, ...)
Sustainable Development Goals (SDGs)

