First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Engineering
Course unit
INP8084178, A.A. 2018/19

Information concerning the students who enrolled in A.Y. 2018/19

Information on the course unit
Degree course Second cycle degree in
IN0521, Degree course structure A.Y. 2009/10, A.Y. 2018/19
bring this page
with you
Number of ECTS credits allocated 9.0
Type of assessment Mark
Course unit English denomination AUTOMATA, LANGUAGES AND COMPUTATION
Department of reference Department of Information Engineering
E-Learning website
Mandatory attendance No
Language of instruction Italian
Single Course unit The Course unit can be attended under the option Single Course unit attendance
Optional Course unit The Course unit can be chosen as Optional Course unit

Teacher in charge GIORGIO SATTA ING-INF/05

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Educational activities in elective or integrative disciplines INF/01 Computer Science 2.0
Core courses ING-INF/05 Data Processing Systems 7.0

Course unit organization
Period First semester
Year 1st Year
Teaching method frontal

Type of hours Credits Teaching
Hours of
Individual study
Lecture 9.0 72 153.0 No turn

Start of activities 01/10/2018
End of activities 18/01/2019
Show course schedule 2019/20 Reg.2009 course timetable

Examination board
Board From To Members of the board
2 A.A. 2019/2020 01/10/2019 15/03/2021 SATTA GIORGIO (Presidente)
PIZZI CINZIA (Membro Effettivo)
1 A.A. 2018/2019 01/10/2018 15/03/2020 SATTA GIORGIO (Presidente)
PINI MARIA SILVIA (Membro Effettivo)
PIZZI CINZIA (Supplente)

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, non-deterministic finite automata, and non-deterministic finite automata with epsilon-transitions. Regular expressions and their relationship to finite state automata. Properties of regular languages.

Context-free grammars and derived trees; simplification of context-free grammars and canonical forms. Push-down automata and their relationship to context-free grammars. Properties of context-free language.

Turing machines: basic definitions and construction techniques. Recursively enumerable (computable) languages/problems, and recursive (decidible) languages. Church-Turing thesis. Proof of the existence of languages/functions that cannot be decided or computed. Intractable problems and the notion of NP-completeness. 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 self-evaluation 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 application-oriented 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 Cerca nel catalogo

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)
Quality Education