[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
- Opta konstrukcija minimalnog automata i
jedinstvenost
- Algoritam za minimizaciju
Literatura
Osnovni udbenik 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]
|