1. komponenta

Lecture type	Total
Lectures	45
Exercises	30

* Load is given in academic hour (1 academic hour = 45 minutes)

COURSE AIMS AND OBJECTIVES:
Enable students to:
- correctly position formal languages, automata and grammars within the Chomsky hierarchy;
- further study computability theory through acquiring a good theoretical foundation and building intuition;
- interpret programs in practice as a natural continuation of the covered theory.

COURSE DESCRIPTION AND SYLLABUS:
I. The Chomsky hierarchy
1. Regular languages: regular expressions, deterministic and nondeterministic finite automata, regular grammars
2. Context-free languages: context-free grammars, pushdown automata
3. Context-sensitive languages: linear bounded automata, monotone and context-sensitive grammars
4. Recursive and recursively enumerable languages: Turing machines (recognizers, deciders, enumerators), unrestricted grammars

II. Introduction to computability
1. Problems and undecidability
2. Some other models of universal computbility (partially recursive functions, lambda calculus, random-access machines)

1. Introduction to the Theory of Computation, 3rd edition, M. Sipser, Cengage Learning, 2013.
2. Izračunljivost, M. Vuković, PMF-Matematički odjel, 2009.
3. Izračunljivost za računarce (https://web.math.pmf.unizg.hr/~veky/izr/Komputonomikon.pdf), V. Čačić.

Mandatory course - Regular study - Computer Science and Mathematics