[Home]   [Program i literatura]   [Zadaci]

M147: TEORIJA AUTOMATA


Okvirni program predmeta

1. Algebra formalnih jezika
  • Reči, jezici, operacije na jezicima, algebre jezika
  • Osnovni identiteti algebri jezika
  • Regularni izrazi i regularni jezici
2. Konačni automati
  • Poluautomati
  • Sintaksni monoid poluautomata
  • Deterministički konačni automati (DKA)
  • Nedeterministički konačni automati (NKA), ekvivalencija NKA i DKA
3. Karakterizacije regularnih jezika
  • Klinijeva teorema: analiza i sinteza automata
  • Pumping lema za regularne jezike
  • Algoritamski problemi za regularne jezike
  • Teorema Majhil-Neroda: desne kongruencije konačnog indeksa

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.
     

 [Home]   [Program i literatura]   [Zadaci]