60/61/122 - AUTOMATA AND FORMAL LANGUAGES

Academic Year 2022/2023

Free text for the University

Objectives

1. Knowledge and comprehension skills.
The course will expose students to the theory of automata and formal languages. In particular, the student will learn some basic techniques on the formal modelling and analysis of software systems, and on the limitations of computing machines. The various topics presented in the course will be supported by formal arguments, allowing students understand the proof of simple properties of formal systems.

2. Ability to apply knowledge and comprehension.
Students will learn some basic skills in the abstraction of practical problems through formal models, and in particular how to
apply simple algorithms on formal languages, and to use some software tools based on the theory of automata.

3. Making judgments.
The course provides students with the basic skills to apply the techniques described during the course to the solution of technical problems related to the topic of the course.

4. Communication skills.
The lectures will include frequent interactions with students, who will learn how to properly communicate the studied topics.

5. Learning skills.
The course provides students with sufficient skills to understand advanced textbooks on the course topic, allowing them to autonomously expand their knowledge.

Prerequisites

Some basic knowledge of discrete math, set theory, mathematical logic and proof techniques, algorithms and data structures is useful.

Contents

- Logical notation
- Sets, functions and bijections
- Recursive definitions and inference rules
- Languages
- Proof procedures for propositional and predicate logic
- Functional programming in Ocaml
- Labelled transition systems
- Finite state automata
- From non-deterministic to deterministic FSAs
- Pumping lemma for regular languages
- Decision procedures for regular languages
- Turing machines
- Non computable functions
- Computational complexity

Teaching Methods

The course consists of 24 classes, of 2 hours each (48 lecturing hours in total). These lectures also include exercises, where students are required to apply the studies techniques. A tutoring course will run in parallel with the main course, to help students in the preparation of the final exam. The lecturer will support students throughout the whole academic year, either through office hours and the elearning site of the course.

Classes will be given in-person. Lectures could be enriched with audio-visual tools and with streaming.

Verification of learning

The exam consists of a written and an oral part, crafted to verify the knowledge and skills acquired by students.

Texts

Reference text: lecturer's notes (in english)

Other suggested texts:

Hopcroft, Motwani, Ullman. Automi, linguaggi e calcolabilita'. Pearson, 2009.

Functional programming in Ocaml: https://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/

More Information

https://elearning.unica.it/course/view.php?id=157