Opšta sekcija
- Predmetni nastavnik: dr Tatjana Stojanović
Saradnici: Filip Andrić
Nastavni plan
- Regularni jezici. Regularne gramatike. Deterministički i nedeterministički konačni automati. Regularni izrazi. Lema napumpavanja za regularne jezike. Svojstva regularnih jezika. Leksička analiza.
- Kontekstno slobodni jezici. Kontekstno-slobodne gramatike. Stabla izvođenja. Lema napumpavanja za kontekstno slobodne jezike. Normalna forma Čimskog. Potisni automati. Deterministički potisni automati. Sintaksna analiza.
- Tjuringove mašine. Varijante Tjuringovih mašina. Gramatike tipa 0. Linearno ograničeni automati i gramatike tipa 1. Rekurzivni i rekurzivno nabrojivi jezici. Odlučivost u teoriji jezika. Formalna analiza.
Način polaganja ispita
- redovno prisustvo nastavi – 4 poena;
- I kolokvijum – 16 poena teorijski deo + 6 poena praktični deo (Lex)
- II kolokvijum – 12 poena teorijski deo + 12 poena praktični deo (Yacc)
- završni ispit – 50 poena.
Student može izaći na završni ispit ako na predispitnim obavezama osvoji najmanje 26 poena i to najmanje 8 na praktičnom delu i najmanje 14 na teorijskom delu.
Na svakom kolokvijumu student mora imati više od 4 poena.
Završni ispit je obavezan.
Na završnom ispitu student odgovara na tri teoretska pitanja. Neophodno je da student za svako postavljeno pitanje pokaže minimum znanja.Organizacija nastave u školskoj 2023/24
Sve infromacije biće dostupne u Teams učionici
Za pristup učionici neophodno je koristiti pmf.kg.ac.rs nalog
Kod za pristup učionici je 27vwach
Literatura
- Z. Ognjanović, N. Krdžavac, Uvod u teorijsko računarstvo, Beograd – Kragujevac
- M. Sipser, Introduction to the theory of computation, Thompson, Course Technology, 2006.
- J.E. Hopcroft, R. Motowani, J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, Massachusetts, 2001.