Formalni jezici i automati

Nastavni program:

• Uvod u teoriju jezika i automata; Matematička lingvistika;
• Konačni automati; Deterministički konačni automati; Nedeterministički konačni automati; Regularni izrazi; Regularni jezici i regularna gramatika; Osobine regularnih jezika;
• Konačni automati s izlazom; Pushdown automati; Nedeterministički i deterministički pushdown automati;
• Kontekstno neovisni jezici i konteksno neovisna gramatika; Tehnike parsiranja;
• Turingova mašina; Turingova teza; Univerzalna Turingova mašina; Nedeterminističke Turingove mašine;
• Rekurzivni i rekurzivno prebrojivi jezici; Linearno ograničeni automat;
• Konteksno ovisni jezici i konteksno ovisna gramatika; Chomskyeva hijerarhija jezika;
• Odlučivi i neodlučivi problemi;
• Kompleksnost automata i jezika;

Literatura:

• Jozef Gruska: Foundations of Computing, International Thomson Computer Press, 1997
• Michael Sipser: Introduction to the Theory of Computation, Course Technology, 2005
• Peter Linz, An Introduction to Formal Languages and Automata, Jones and Bartlett Publishers, 2000
• Martin, John, Introduction to Languages and the Theory of Computation, McGraw-Hill, 1997