Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu maghiară
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MIF0003	Formális nyelvek és fordítóprogramok	

Félév	Órák: C+S+L+P	Kategória	Típus	
5	2+1+2+0	szaktárgy	kötelező	

II. Főállású oktatók
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
EGRI Edith	Dr.	adjunktus	Informatikai rendszerek	*		*	

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	

III. A tantárgy célkitűzései
A tantárgy célja megismertetni a hallgatókkal a formális nyelvek és automaták alapfogalmait, algoritmusait, amelyek használatosak a fordítóprogramok esetében, bevezetni őket a fordítóprogramok tervezésének és megvalósításának tudományába.  
A szemináriumokon az elméleti tudást gyakorlati feladatokon mélyítjük el. A gyakorlati órákon konkrét algoritmusokat programoznak.	

IV. A tantárgy tartalma
Formális nyelvek:
Formális nyelvtanok, nyelvek, alapfogalmak, Chomsky-féle nyelvosztályok
Normálalakok, kiterjesztett nyelvtanok
Véges automaták és reguláris nyelvek 
Reguláris nyelvek, pumpáló lemma reguláris nyelvekre
Reguláris kifejezések
Veremautomaták és környezetfüggetlen nyelvek
Turing-automaták és algoritmikusan megoldható feladatok
Speciális nyelvtanok és nyelvek (LL(k) nyelvtanok, LR(k) nyelvtanok, elsőbbségi (precedencia) nyelvtanok)
Fordítóprogramok:
Fordítóprogramok szerkezete
Lexikális, szintaktikai és szemantikai elemzések
Felülről lefelé és alulról felfelé történő elemzések
Kódgenerálás és kódoptimalizálás	

V. Könyvészet
1. Fülöp Zoltán, Formális nyelvek és szintaktikus elemzésük,  Polygon, Szeged, 1999.
2. Kása Zoltán: Formális nyelvek és automaták, Kolozsvár, 2004. Egyetemi jegyzet
3. Aho, A. V., Ullmann, J. D.: The Theory of Parsing, Translation and Compiling, Vol  I-II., Prentice-Hall, 1972—1973
4. Csörnyei Zoltán, Fordítópogramok, Typotex Kiadó, Budapest, 2006.
5. Demetrovics János, Denev, J.,  Pavlov, R.,  A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999.
6. Manna, Z., Programozáselmélet,  Műszaki Könyvkiadó, Budapest, 1981.
7. Moldovan, G., Cioban, V., Lupea, M, Limbaje formale si teoria automatelor. Culegere de probleme}, Editura Mesagerul, Cluj-Napoca,  1997.
8. Moldovan, G.: Limbaje formale si teoria automatelor, EduSoft, 2005.	

VI. Az oktatói tevékenység heti tematikája
1. előadás:  Formális nyelvtanok, nyelvek, alapfogalmak, Chomsky-féle nyelvosztályok
2. előadás:  Normálalakok, kiterjesztett nyelvtanok
3–4. előadás: Véges automaták és reguláris nyelvek (determinisztikus és nemdeterminisstikus automaták, műveletek véges automatákkal, minimalizálás)
5. előadás:.Reguláris nyelvek, pumpáló lemma reguláris nyelvekre
6. előadás: Reguláris kifejezések
7–8. előadás: Veremautomaták és környezetfüggetlen nyelvek
9. előadás: Turing-automaták és algoritmikusan megoldható feladatok
10. előadás: Speciális nyelvtanok és nyelvek (LL(k) nyelvtanok, LR(k) nyelvtanok, elsőbbségi (precedencia) nyelvtanok)
11. előadás:  Fordítóprogramok szerkezete
12. előadás: Lexikális, szintaktikai és szemantikai elemzések
13. előadás: Felülről lefelé és alulról felfelé történő elemzések
14. előadás: Kódgenerálás és kódoptimalizálás

Gyakorlatok:
1. determinisztikus véges automata ábrázolása
2. determinisztikus véges automaták ekvivalenciája
3. determinisztikus véges automaták minimalizálása
4.-5. nemdeterminisztikus véges automata ábrázolása
6. veremautomata ábrázolása
7. lexikális elemző
8.-10. alulról felfele elemzők
11.-14 felülről lefele elemzők	

VII. Alkalmazott didaktikai módszerek
kifejtés, problematizálás	

VIII. Értékelés

A hallgatók tevékenységét a szemináriumokon és a gyakorlati órákon állandóan ellenőrizzük. A végleges jegyben 
50% súllyal szerepel az írásbeli vizsga, 
25% súllyal a szemináriumi és 
25% súllyal a laboratóriumi tevékenység.	

IX. Kiegészítő könyvészet
1. Gécseg Ferenc, Peák István, Algebraic Theory of Automata,  Akadémiai Kiadó,  Budapest, 1972.
2. Hopcroft, J. E., Ullmann, J. D., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
3. Révész György, Bevezetés a formális nyelvek elméletébe,  Akadémiai Kiadó, Budapest, 1979.
4. Motogna Simona: Metode de proiectare a compilatoarelor, Ed. Albastra, Cluj, 2006.
5. Iványi Antal (szerk.) Informatikai algoritmusok II., ELTE-Eötvös Kiadó, Budapest, 2005.
6. http://www.ms.sapientia.ro/~kasa/formalis.htm	

	Dátum,						Az előadás felelőse,
	2010. nov. 22.						Dr. EGRI Edith adjunktus