OVERVIEW

The teaching presents concepts and results of Automata Theory and of Computability Theory of fundamental importance in the cultural background of 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. 

AIMS AND LEARNING OUTCOMES

At the end of the teaching the student/student will be able to:

• Know some fundamental concepts and results in the culture of acomputer science (abstract machine, language recognition, computable function, decidability, haltingproblem).
• Develop simple automata, including through the use of simulators.

PREREQUISITES

• Basics of sets and functions
• Programming experience in some language.

TEACHING METHODS

Traditional.

Students who hold valid certificates relating to Specific Learning Difficulties (SLD), disabilities or other educational needs are invited to contact the lecturer and the school’s disability liaison officer at the start of the course to agree on any teaching arrangements which, whilst respecting the course objectives, take into account individual learning styles. 

The contact details for the university’s disability liaison officer are available at the following link: https://unige.it/commissioni/comitatoperlinclusionedeglistudenticondisabilita. 

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, deterministic and non deterministic push down automata (PDA)
Closure properties of context-free languages, pumping lemma

Computability
Turing machines, accepted languages
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

RECOMMENDED READING/BIBLIOGRAPHY

Course notes.

TEACHERS AND EXAM BOARD

LESSONS

LESSONS START

According to the calendar approved by the Degree Program Board:https://easyacademy.unige.it/portalestudenti/index.php?view=easycourse&_lang=it&include=corso

Class schedule

The timetable for this course is available here: Portale EasyAcademy

EXAMS

EXAM DESCRIPTION

The examination consists of a written test and an oral test. In order to take the oral test, it is necessary to have passed the written test.

Guidelines for students with certified Specific Learning Disorders, disabilities, or other special educational needs are available at https://corsi.unige.it/en/corsi/8759/studenti-disabilita-dsa 

ASSESSMENT METHODS

The written test verifies the student's ability to put into practice the concepts seen in class. The oral test verifies the understanding of the concepts and the ability to illustrate them in   appropriate way.

FURTHER INFORMATION

For further information, please refer to the course’s AulaWeb module or contact the instructor.

Students with valid certifications for Specific Learning Disorders (SLD) may request accommodations for exams at least 7 days prior to the exam date by filling out the “accommodation request form” (available via online services at https://modulionline.unige.it/richiesta-adattamenti# no-back), which will be automatically forwarded by the system to the instructor in charge of the course and to the faculty liaison for students with disabilities and SLDs in their School/Department. 

The student will receive a copy of their request.