OVERVIEW

We introduce notions and results from Automata Theory and Computability Theory which are of paramount importance for a computer scientist.

AIMS AND CONTENT

LEARNING OUTCOMES

To understand key concepts of Theory of Automata and Theory of Computability, such as expressive power of automata, and decidability and semi-decidability of problems. 

SYLLABUS/CONTENT

Automata and Languages
Alphabets, strings, languages
Deterministic (DFA) and non deterministic (NFA) finite state automata
DFA minimization, regular expressions

Closure properties of regular languages, pumping lemma
Context-free grammars, derivation trees, ambiguity
Deterministic and non deterministic push down automata (PDA)
Closure properties of context-free languages, pumping lemma

Computability
Turing machines, accepted languages
Non deterministic Turing machines
Semi-infinite tapes
Multi-stack, counter machines
Indecidability, recursive and recursively enumerable languages, universal language and machine, indecidability of the universal language
Halting problem
Indecidable problems on Turing machines, Rice theorem, Church thesis

TEACHERS AND EXAM BOARD

Exam Board

ELENA ZUCCA (President)

DAVIDE ANCONA

GIORGIO DELZANNO

EUGENIO MOGGI

LESSONS

Class schedule

FOUNDATIONS OF COMPUTER SCIENCE

EXAMS

Exam schedule