First cycle
degree courses
Second cycle
degree courses
Single cycle
degree courses
School of Science
COMPUTER SCIENCE
Course unit
AUTOMATA AND FORMAL LANGUAGES
SC03100756, A.A. 2018/19

Information concerning the students who enrolled in A.Y. 2017/18

Information on the course unit
Degree course First cycle degree in
COMPUTER SCIENCE
SC1167, Degree course structure A.Y. 2011/12, A.Y. 2018/19
N0
bring this page
with you
Number of ECTS credits allocated 8.0
Type of assessment Mark
Course unit English denomination AUTOMATA AND FORMAL LANGUAGES
Website of the academic structure http://informatica.scienze.unipd.it/2018/laurea
Department of reference Department of Mathematics
Mandatory attendance No
Language of instruction Italian
Branch PADOVA
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

Lecturers
Teacher in charge GILBERTO FILE' INF/01
Other lecturers DAVIDE BRESOLIN INF/01

ECTS: details
Type Scientific-Disciplinary Sector Credits allocated
Core courses INF/01 Computer Science 8.0

Course unit organization
Period Second semester
Year 2nd Year
Teaching method frontal

Type of hours Credits Teaching
hours
Hours of
Individual study
Shifts
Practice 2.0 16 34.0 No turn
Lecture 6.0 48 102.0 No turn

Calendar
Start of activities 25/02/2019
End of activities 14/06/2019

Examination board
Board From To Members of the board
7 a.a. 2017/2018 01/10/2017 28/02/2019 FILE' GILBERTO (Presidente)
BALDAN PAOLO (Membro Effettivo)
BRESOLIN DAVIDE (Membro Effettivo)
CRAFA SILVIA (Membro Effettivo)
RANZATO FRANCESCO (Membro Effettivo)

Syllabus
Prerequisites: Basic notions of logic.
Target skills and knowledge: This course provides the fundamental concepts of automata theory and formal languages, showing their application to compilers. Moreover, it introduces the notions of indecidability and intractability.
Examination methods: Written exam.
Assessment criteria: The written examination contains questions that allow to evaluate the level of comprehension of the notions taught during the course. There are also exercises about automata and formal grammars.
Course unit contents: The main topics of the course are:

Part 1: regular languages and lexical analysis (3 cfu)
-- finite state automata
-- regular expressions and regular languages
-- pumping lemma
-- properties of regular languages
-- lexical analysis

Part 2: context-free languages and syntactic analysis (3 cfu)
-- context-free grammars and languages
-- pushdown automata
-- pumping lemma
-- properties of context-free languages
-- syntactic analysis

Part 3: undecidability and intractability (2 cfu)
-- Turing machines
-- indecidability
-- intractable problems
-- classes P and NP
Planned learning activities and teaching methods: Lectures and exercises in classroom.
Additional notes about suggested reading: A moodle platform contains all material of the course. The lessons are recorded and available to students.
Textbooks (and optional supplementary readings)
  • Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Automi, linguaggi e calcolabilità. Milano: Addison-Wesley Pearson Education Italia, 2009. Cerca nel catalogo
  • Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools. --: Addison-Wesley, 2006. Cerca nel catalogo

Innovative teaching methods: Teaching and learning strategies
  • Lecturing
  • Problem based learning
  • Interactive lecturing
  • Problem solving
  • Auto correcting quizzes or tests for periodic feedback or exams
  • Active quizzes for Concept Verification Tests and class discussions
  • Video shooting made by the teacher/the students

Innovative teaching methods: Software or applications used
  • Moodle (files, quizzes, workshops, ...)
  • Camtasia (video editing)

Sustainable Development Goals (SDGs)
Industry, Innovation and Infrastructure