C8648 - LINGUISTICA FORMALE E MODELLI COMPUTAZIONALI

Learning outcomes

Upon completion of the course, students will know: - grammars, their Chomsky classification, the equivalence of regular expressions/grammars with their respective automata classes, and their use in linguistics to express lexicon and syntax; - fundamental aspects of logics, deductive systems, temporal logics, and their use in describing and verifying properties of concurrent/distributed systems.

Course contents

Automata and formal languages:
- finite state automata
- regular expressions and their relationship with finite state automata
- context free grammars and Cocke-Younger-Kasami algorithm
- pushdown automata and their relationship with context free grammars
- Chomsky classification of grammars

Applications to formal linguistics:
- probabilistic context free grammars
- probabilistic regular grammars and their relationship with finite state automata
- probabilistic variants of the Cocke–Younger–Kasami algorithm
- use of these models in linguistics to represent lexicon and syntax

Basic logic:
- propositional logic
- deduction systems
- predicate logic

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. Pearson Education Resources Italia S.R.L, 2021.
AlmaStart Unibo Link (available online)

Russell, Norvig. "Artificial Intelligence: A Modern Approach", 4th edition, Global Edition. Pearson International, 2022.
AlmaStart Unibo Link (available online)

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

Teaching methods

Lectures with whiteboard/PC/beamer and experiences in laboratory.

As concerns the teaching methods of this course unit, all students must attend Module 1, 2 on Health and Safety online.

Assessment methods

The final assessment consists of a written examination, graded on a 30-point scale, 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.

Regarding assessment, the use of AI is prohibited. Any use of AI constitutes a violation of academic integrity.

Teaching tools

Whiteboard, PC, beamer, computer laboratory.

Office hours

See the website of Mario Bravetti