[Home]   [Program i literatura]   [Ispitni zadaci]

M185: TEORIJA AUTOMATA

Program predmeta

• Reči, jezici, operacije na jezicima, algebre jezika
• Osnovni identiteti algebri jezika
• Regularni izrazi i regularni jezici

• Poluautomati
• Sintaksni monoid poluautomata
• Deterministički konačni automati (DKA)
• Nedeterministički konačni automati (NKA), ekvivalencija NKA i DKA

• Klinijeva teorema: analiza i sinteza automata
• Pumping lema za regularne jezike
• Algoritamski problemi za regularne jezike
• Teorema Majhil-Neroda: desne kongruencije konačnog indeksa
• Sintaksna kongruencija i prepoznavanje konačnim monoidima

4. Minimalni automati

• Opšta konstrukcija minimalnog automata i jedinstvenost
• Algoritam za minimizaciju

Literatura

Osnovni udžbenik za ovaj predmet je:

• R.Sz.Madarász, S.Crvenković, Uvod u teoriju automata i formalnih jezika, Prirodno-matematički fakultet, Stylos, Novi Sad, 1995.

Osim toga, na raspolaganju je i zbirka zadataka:

• S.Crvenković, R.Sz.Madarász, N.Mudrinski, Zbirka zadataka iz teorije automata, Prirodno-matematički fakultet, Novi Sad, 2005.

Od strane literature, zainteresovanim studentima preporučujem sledeća dva naslova:

• J.E.Hopcroft, R.Motwani, J.D.Ullman, Introduction to Automata Theory, Languages, and Computation (2nd ed.), Addison-Wesley, Reading, 2001.

• D.C.Kozen, Automata and Computability, Springer-Verlag, New York, 1997.

kao i skripte (u pdf formatu):

• J.Karhumäki: Automata and Formal Languages, Turku, 2007.

[Home]   [Program i literatura]   [Ispitni zadaci]