Teorija algoritama, automata i jezika

Alfabet, reč i jezik nad alfabetom. Formalne gramatike. Jezik definisan gramatikom. Hijerarhija formalnih gramatika prema Čomskom.

Regularni jezici. Deterministički konačni automati. Nedeterministički konačni automati. NKA sa spontanim prelazima. Regularni izrazi. Ekvivalentnost DKA, NKA i regularnih izraza. Minimizacija DKA. Pumping lema za regularne jezike.

Kontekstno-slobodni jezici. Potisni automati. Deterministički potisni automati. Ekvivalentnost potisnih automata i kontekstno-slobodnih jezika. Osobine kontekstno-slobodnih jezika. Normalna forma Čomskog za kontekstno-slobodne gramatike. Pumping lema za kontekstno-slobodne jezike.

Tjuringova mašina. Tjuringova mašina sa više traka. Nedeterministička Tjuringova mašina. Neodlučivost. Rekurzivno nabrojivi i rekurzivni jezici.

Klase problema P i NP, NP-kompletni problemi. Doka NP-kompletnosti problema CSAT i 3SAT.