Predmet osposobljava studente za primjenu formalnih modela u inženjerstvu za potrebe oblikovanja računalnih i komunikacijskih procesa, protokola i sustava. Studenti će biti sposobni na osnovi definicije problema izraditi formalni model, ispitati valjanost, procijeniti učinkovitost i složenost, programski ili sklopovski ostvariti te dokumentirati i ispitati predloženo rješenje. Nadalje, studenti stječu dovoljno osnovnih znanja za daljnje proučavanje teorije složenih računalnih procesa i sustava.

1. opisati ponašanje računalnog sustava i komunikacijskog protokola formalnim jezikom
2. dizajnirati računalni proces primjenom formalnog modela
3. primijeniti formalne modele za provjeru valjanosti računalnog sustava
4. klasificirati problem s obzirom na Chomskyevu hijerarhiju formalnih jezika
5. odabrati formalni model optimalne složenosti za potrebe opisa, oblikovanja i izgradnje računalnog sustava
6. ocijeniti vremensku i prostornu složenost računalnog procesa
7. ocijeniti učinkovitost računalnog sustava i komunikacijskog protokola

Predavanja popraćena PowerPoint projekcijom, praktični primjeri primjene formalnih jezika, automata i gramatika

Dva pismena ispita

Rješavanje zadataka popraćeno PowerPoint projekcijom, priprema za pismene provjere znanja

Programsko ostvarenje algoritama vezanih uz teoriju formalnih jezika, automata i gramatika. Programsko ostvarenje praktične primjene automata i gramatika. Online predaja i automatsko ocjenjivanje studentskih rješenja.

Pojedinačne konzultacije s nastavnicima i asistentima organiziraju se po potrebi na zahtjev studenta.

1. Znak, abeceda, niz i formalni jezik; Primjer formalnog jezika, automata i gramatike; ([1], str. 1-14) Deterministički konačni automat: primjer i definicija; Deterministički konačni automat: programsko ostvarenje i minimizacija; ([1], str. 15-29)
2. Determinizam i nedeterminizam; Nedeterministički konačni automat; Nedeterministički konačni automat s e-prijelazima; ([1], str. 29-39) Konačni automati s izlazom; Regularni izrazi; Generator konačnog automata; ([1], str. 39-51)
3. Svojstva regularnih jezika; Formalna gramatika: primjer i definicija; Regularna gramatika; ([1], str. 51-63) Regularna gramatika (nastavak); Kontekstno-neovisni jezici; Kontekstno-neovisna gramatika; Nejednoznačnost gramatike i jezika; Pojednostavljenje kontekstno-neovisne gramatike; ([1], str. 63-78)
4. Pojednostavljenje kontekstno-neovisne gramatike (nastavak); ([1], str. 78-88) Prepoznavanje i parsiranje niza; Programsko ostvarenje parsiranja od vrha prema dnu; Tehnika rekurzivnog spusta; Parsiranje od dna prema vrhu; LR parsiranje; ([1], str. 89-102)
5. Potisni automat: primjer i definicija; ([1], str. 103-114) Potisni automat (nastavak); Svojstva kontekstno-neovisnih jezika; ([1], str. 114-125)
6. Auditorne vježbe: regularni jezici;
7. Auditorne vježbe: kontekstno-neovisni jezici;
8. Prvi međuispit: regularni jezici, kontekstno-neovisni jezici;
9. Rekurzivno-prebrojivi jezici; Turingov stroj; Metode izrade Turingovog stroja; ([1], str. 126-138) Prošireni modeli Turingovog stroja; ([1], str. 139-146)
10. Pojednostavljeni modeli Turingovog stroja; Generiranje jezika Turingovim strojem; ([1], str. 146-151) Gramatika neograničenih produkcija; Svojstva rekurzivnih jezika i rekurzivno-prebrojivih jezika; Izračunljivost; Odlučivost; ([1], str. 152-164)
11. Kontekstno-ovisni jezici; Kontekstno-ovisna gramatika; Linearno ograničeni automat; Svojstva kontekstno-ovisnih jezika; ([1], str. 165-172) Svojstva kontekstno-ovisnih jezika (nastavak); Chomskyeva razredba formalnih jezika, gramatika i automata; Definicija prostorne i vremenske složenosti; Složenost automata i jezika; Svojstva funkcija prostorne i vremenske složenosti; ([1], str. 173-187)
12. Razredi problema s obzirom na složenost; ([1], str. 187-190) Svojstva hijerarhije jezika s obzirom na složenost; ([1], str. 190-194)
13. Razredi problema polinomne složenosti; Učinkovitost; Postupak svođenja; Definicija potpunih i teških problema; P-potpuni (teški) i NP-potpuni (teški) problemi; ([1], str. 194-199)
14. Auditorne vježbe: rekurzivno-prebrojivi jezici, kontekstno-ovisni jezici, teorija složenosti;
15. Završni ispit: cjelokupno gradivo predmeta;