81609 - Languages, Compilers and Computational Models

Learning outcomes

At the end of the course the student knows: - foundational aspects of logics, automata, regular expressions and grammars - techniques for the design and implementation, via compilers, of programming languages - languages, models and techniques for the description and property verification of concurrent and distributed software systems.

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

Basic logic:
- propositional logic
- predicate logic

Compilers: 
- lexical analyzers 
- syntactic analyzers and syntax directed translation 
- static program checking 
- code generation 

Computational models:
- transition systems for the modeling of system behavior
- temporal logics for property specification and verification
- concurrent finite state processes with synchronization and interleaving
- Petri nets

Readings/Bibliography

Hopcroft, Motwani, Ullman. "Automi, Linguaggi e Calcolabilità", terza edizione. Addison-Wesley, 2009.

Aho, Lam, Sethi, Ullman. "Compilatori: principi, tecniche e strumenti", seconda edizione. Addison-Wesley, 2009.

Huth, Ryan. "Logic in Computer Science: Modelling and Reasoning about Systems", second edition. Cambridge University Press, 2004.

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