1. komponenta

Vrsta nastave	Ukupno
Predavanja	45
Auditorne vježbe	30

* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)

CILJ KOLEGIJA:
Studente osposobiti za:
- pravilno smještanje formalnih jezika, automata i gramatika u Chomskyjevu hijerarhiju;
- daljnje usmjeravanje u teoriji izračunljivosti kroz stjecanje temeljnih teorijskih znanja i izgradnju intuicije;
- praktičnu interpretaciju programa kao prirodan nastavak obrađene teorije.

NASTAVNI SADRŽAJI:
I. Chomskyjeva hijerarhija
1. Regularni jezici: regularni izrazi, deterministički i nedeterministički konačni automati, linearne gramatike.
2. Beskontekstni jezici: beskontekstne gramatike, potisni automati.
3. Kontekstni jezici: ograničeni automati, monotone i kontekstne gramatike.
4. Rekurzivni i rekurzivno prebrojivi jezici: Turingovi strojevi (prepoznavači, odlučitelji i enumeratori), opće gramatike.

II. Uvod u izračunljivost
1. Problemi i neodlučivost.
2. Neki drugi modeli opće izračunljivosti (parcijalno rekurzivne funkcije, lambda-račun, RAM strojevi).

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ć.

Obavezni predmet - Redovni Studij - Računarstvo i matematika