Uvod u formalne jezike i automate
ISVU: 52661•6 ECTS•Zimski semestar
Osnovne informacije
- Organizacijska jedinica
- Odsjek za informacijske i komunikacijske znanosti
- Satnica
- Predavanja: 15 sati
- Seminar: 15 sati
- Vježbe u praktikumu: 30 sati
Nastavnici
Cilj
Opće i specifične kompetencije (znanje i vještine)
Student će dobiti temeljna znanja iz discipline formalnih jezika, posebno regularnih izraza, gramatika i automata, neophodna za primjenu u identifikaciji tipa jezika i definiranju njegove specifikacije (sintakse) izborom odgovarajućeg formalizma.
Sadržaj
- Uvod u teoriju formalnih jezika.
- Regularni skupovi i izrazi.
- Konačni stroj
- Linearni jezici
- Gramatike: definicija gramatike, gramatika kao generator jezika, rečenična forma, niz izvođenja, klasifikacija gramatika, prikaz gramatika, transformiranje gramatika.
- Beskontekstni jezici
- Stogovni automat
- Kontekstni jezici
- Turingov stroj
- Rekurzivno nabrojivi jezici
- Rad na seminarskom zadatku
- Rad na seminarskom zadatku.
- Rad na seminarskom zadatku.
- Rad na seminarskom zadatku.
- Rad na seminarskom zadatku.
Ishodi učenja
- Definirati pojam formalnoga jezika.
- Koristiti regularne izraze
- Primjenjivati automate
- Modelirati gramatiku jezika
- Primijeniti stečena znanja u drugim predmetima studija.
Metode podučavanja
Predavanja: kombinirano, klasično (ploča) i prikazom primjera izvedbom na PCu
Vježbe: rješavanje postavljenih zadataka.
Seminar: pisanje zadanog seminarskog rada uz konzultiranje s predmetnim nastavnikom.
Metode ocjenjivanja
Dva kolokvija koja služe umjesto pismenoga ispita, seminarski rad i usmeni ispit.
Obavezna literatura
- Zdravko Dovedan Han: FORMALNI JEZICI I PREVODIOCI - regularni izrazi, gramatike, automati, Element Zagreb 2012.
- Dovedan, Z.: FORMALNI JEZICI • sintaksna analiza, Zagreb, ZIS, 2003.
Dopunska literatura
- Aho, V. A.; Ullman, D. J.: The Theory of Parsing, Translation, and Compiling, vol. I: Parsing, Prentice-Hall, 1972.