Naziv kolegija: Uvod u formalne jezike i automate
Nastavnik: prof. dr. sc. Zdravko Dovedan Han
ECTS-bodovi: 6
Jezik: hrvatski
Trajanje: jedan semestar (5.)
Status: obavezan za studente jednopredmetnog preddiplomskog studija Informacijskih znanosti, izborni za ostale studije
Oblik nastave: 1 sat predavanja - 2 sata seminara - 1 sat vježbi
Uvjeti: Algoritmi i strukture podataka
Ispit: pismeni i usmeni
Sadržaj
Uvod u teoriju formalnih jezika: znakovi i nizovi znakova, definicija formalnog jezika, operacije nad jezicima, simboli i nizovi simbola, klasifikacija jezika, definiranje jezika. Regularni skupovi i izrazi. Gramatike: definicija gramatike, gramatika kao generator jezika, rečenična forma, niz izvođenja, klasifikacija gramatika, prikaz gramatika, transformiranje gramatika. Automati: automati i jezici, konačni automat, deterministički i nedeterministički automat, konačni generatori, konačni generatori i regularni izrazi. Linearni jezici: linearne gramatike, izvođenje gramatika linearnih jezika, izvođenje linearnih gramatika iz regularnih izraza, konačni automati i linearne gramatike. Beskontekstni jezici: svojstvo beskontekstnih jezika, beskontekstne gramatike, transformiranje beskontekstnih gramatika, stogovni automati, ekvivalentnost stogovnih automata i beskontekstnih gramatika, stogovni automat s praznim stogom, izvođenje beskontekstnih gramatika. Kontekstni jezici: indeksirane gramatike, kontekstne gramatike, graf izvođenja, dvostruko-stogovni automat, ekvivalentnost dvostruko-stogovnih automata i kontekstnih gramatika, dvostruko-stogovni automat s jednim stanjem, izvođenje gramatika kontekstnih jezika. Jezici bez ograničenja: gramatike bez ograničenja, Turingov stroj, Turingov generator, izvođenje gramatika bez ograničenja. Jezici sa svojstvima: sintaksa i semantika, atributne gramatike, generator jezika sa svojstvima.
Sadržaj vježbi
Vježbe slijede predavanja. Sva teorijska razmatranja i definicije upotpunjavaju se odgovarajućim primjerima. Svi se algoritmi implementiraju u jeziku Python.
Sadržaj seminara
Rješavanje individualnog projektnog zadatka izradom praktičnog programskog rješenja u jeziku Python. Student predstavlja svoj rad u pisanom obliku i brani ga usmeno pred predmetnim nastavnikom.
Opće i specifične kompetencije
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.
Ishodi učenja
Nakon uspješno savladanog predmeta, student će moći:
1) Definirati pojam jezika.
2) Definirati regularni izraz danog regularnog jezika.
3) Modelirati gramatiku jezika bilo kojeg tipa.
4) Modelirati generator jezika bilo kojeg tipa.
5) Primijeniti stečena znanja u drugim predmetima studija.
Način održavanja nastave
- Predavanja: kombinirano, klasično (ploča) i prikazom primjera izvedbom na PCu i projiciranjem uz istodobno pisanje primjera programa od strane studenata na svojim računalima.
- Vježbe: rješavanje postavljenih zadataka i pisanje programa na računalu.
- Seminar: rješavanje zadanog projektnog (seminarskog) rada uz konzultiranje s predmetnim nastavnikom.
Obveze studenata i uvjeti
Obvezno pohađanje nastave (predavanja i vježbi).
Način provjere znanja
Praćenje rada i aktivnosti studenata tijekom semestra:
- pohađanje predavanja – 10 bodova,
- posebna isticanja na vježbama – do 10 bodova.
Seminarski rad:
- Obrana seminarskog rada – 80 bodova
Skala ocjena:
dovoljno (2) 50% - 59%
dobro (3) 60% - 69%
vrlo dobro (4) 70% - 79%
izvrsno (5) 80% - 100%
Obavezna literatura
- Dovedan Han, Z.: FORMALNI JEZICI I PREVODIOCI • regularni izrazi, gramatike, automati, Element, Zagreb, 2012.
Preporučena literatura
-
Aho, V. A.; Ullman, D. J.: The Theory of Parsing, Translation, and Compiling, vol. I: Parsing,
Prentice-Hall, 1972. - Denning, J. P.; Dennis, B. J.; Qualitz, E. J.: Machines, Languages, and Computation, Prentice-Hall, 1978.
- Dovedan, Z.: FORMALNI JEZICI • sintaksna analiza, Zagreb, ZIS, 2003.
- Dovedan Han, Z.: Pascal s tehnikama programiranja (1), VVG, Velika Gorica, 2011.
-
Hopcroft, E. J.; Ullman, D. J.: Introduction to Automata Theory, Languages, and Computation,
Addison-Wesley, 1979.
