- Docente: Mario Bravetti
- Credits: 12
- SSD: INF/01
- Language: Italian
- Teaching Mode: In-person learning (entirely or partially)
- Campus: Cesena
- Corso: Second cycle degree programme (LM) in Computer Science and Engineering (cod. 8614)
Learning outcomes
At the end of the course the student will know the foundational aspects related to automata, regular expressions, grammars and techniques for the design and implementation of programming languages. Also languages, models and techniques for the description and property verification of concurrent and distributed software systems will be covered.
Course contents
Automata and formal languages:
- finite state automata
- regular expressions and their relationship with finite state
automata
- context free grammars
- pushdown automata and their relationship with context
free grammars
- Turing machines
- recursive and recursively enumerable languages and their
relationship with Turing machines
- undecidable problems for context free languages
Programming languages:
- lexical analyzers
- syntactic analyzers and syntax directed
translation
- static program checking
- code generation
Computational models:
- finite state automata for the modeling of the system's
behavior
- temporal logics for property specification and verification
- concurrent finite state processes with synchronization and
interleaving
- Petri nets
Readings/Bibliography
Hopcroft, Motwani, Ullman. "Introduction to Automata Theory,
Languages, and Computation", third
edition. Addison-Wesley, 2006.
Aho, Lam, Sethi, Ullman. "Compilers: Principles, Techniques, and
Tools ", second edition. Addison-Wesley, 2006.
Teaching methods
Lectures with whiteboard/PC/beamer and experiences in laboratory.
Assessment methods
The final examination will be a written test with two kinds of
questions:
- theoretical questions aiming at the verification of the
assessment of the theoretical concepts;
- exercises aiming at the verification of the ability to apply the
theoretical concepts on simple use-cases.
An additional project will be used to verify the ability of the
student to implement programming languages.
Teaching tools
Whiteboard, PC, beamer, computer laboratory.
Office hours
See the website of Mario Bravetti