Automati i formalni jezici DR1-02
Beskontekstni jezici. Kontekstno osjetljivi jezici. Stablo izvoda. Gramatike i strojevi: hijerarhija Chomskog, svojstva zatvorenosti, regularni i konačni jezici. Potisni automati i beskontekstne gramatike. Parsing. Turingov stroj i teorija jezika. Principi čvrste točke u teoriji jezika. Indukcije. Vrste semantika: operacijska, obilježna i aksiomatska. Izračunljivost. Problem zaustavljivosti i neodlučnosti. Goedelov teorem. Church – Turingova teza.
Teacher: Ivica Crnković, Josip Job