[Home]
[Program i literatura]
MA411: TEORIJA FORMALNIH
JEZIKA
Program predmeta
1. Generativne gramatike i njihova klasifikacija
- Reči, jezici, operacije na jezicima, algebre
jezika
- Generativne gramatike i hijerarhija Čomskog:
tipovi 3,2,1,0
- Regularni jezici i gramatike tipa 3
2. Kontekstno slobodni jezici
- Kontekstno-slobodne gramatike, drvo izvođenja
- Normalne forme CF gramatika
- Osobine CF jezika: pumping lema,
Parihova teorema, CKY algoritam za problem pripadnosti
- Pushdown automati
3. Kontekstno osetljivi jezici
- Rastuće gramatike i CS jezici, normalna forma
CS gramatike
- Linearno ograničeni automati
4. Tjuringove mašine, rekurzivno nabrojivi i
rekurzivni jezici
- Tjuringove mašine
- Pojam algoritma i Čerčova teza
- Gramatike tipa 0, rekurzivno nabrojivi i
rekurzivni jezici
- Univerzalna Tjuringova mašina
- Neodlučivi problemi
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.
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):
[Home]
[Program i literatura]