Formalni jezici i jezični procesori I

Studij: Diplomski studij Fizika i informatika
Godina: II.
Semestar: zimski
Broj sati u semestru (P+V+S): 30+30+0
Status predmeta: izborni
ECTS: 5

Opis predmeta:  .pdf

Izvedbeni program:  .pdf

Sadržaj
Osnovni pojmovi: Nizovi znakova, abecede, jezici. Modeli simboličkih zapisa: graf, usmjereni graf, stablo. Relacije.
Regularni izrazi, jezici i gramatike. Konačni automati: DKA. NKA. Epsilon-NKA, automati s izlazom. Postupci minimizacije automata. Transformacije automata.
Kontekstno neovisni jezici i gramatike: Nejednoznačnost gramatike.
Pojednostavljenje gramatike.
Potisni automat. Svojstva kontekstno neovisnih jezika.
Rekurzivno prebrojivi jezici. Turingov stroj. Rad Turingova stroja. Rješivi i nerješivi postupci. Izračunljivost jezika. Churchov teorem.
Kontekstno ovisni jezici. Linearno ograničeni automati.
Chomskyeva klasifikacija jezika.

Obvezna literatura
  1. S. Srbljić. Jezični procesori 1, Element, Zagreb, 2002.
  2. J. E. Hopcroft, J. D. Ullman. Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.