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

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MIF0003	Limbaje formale şi tehnici de compilare – 
Formális nyelvek és fordítóprogramok	

Félév	Órák: C+S+L	Kategória	Típus	
3	2+1+1	szak	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	
		Prof.	Informatikai Rendszerek	*			

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	
KÁSA Zoltán	Dr.	Univ. Sapientia	prof	*			

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 és automaták: 
Formális nyelvtanok, nyelvek, alapfogalmak; Chomsky-féle nyelvosztályok; Normálalakok, kiterjesztett nyelvtanok; Véges automaták: nemdeterminisztikus, determiniosztikus, epszilon-lépéses automaták; Véges automaták és reguláris nyelvek ekvivalenciája; Pumpáló lemma reguláris nyelvekre
Reguláris kifejezések; Veremautomaták és környezetfüggetlen nyelvek, normálalakok;
Pumpáló lemma környezetfüggetlen nyelvekre; Speciális nyelvtanok és nyelvek 
Fordítóprogramok:
Fordítóprogramok szerkezete, lexikális elemzés; Szintaktikai elemzések; Szemantikai elemzések; Kódgenerálás és kódoptimalizálás	

V. Könyvészet
1. Csörnyei Zoltán, Kása Zoltán, Formális nyelvek és fordítóprogramok, Presa Universitara Clujeana, 2007
2. Fülöp Zoltán, Formális nyelvek és szintaktikus elemzésük,  Polygon, Szeged, 1999.
3. Kása Zoltán: Formális nyelvek és automaták, Kolozsvár, 2004. Egyetemi jegyzet
4. Aho, A. V., Ullmann, J. D.: The Theory of Parsing, Translation and Compiling, Vol  I-II., Prentice-Hall, 1972—1973
5. Csörnyei Zoltán, Fordítópogramok, Typotex Kiadó, Budapest, 2006.
6. Demetrovics János, Denev, J.,  Pavlov, R.,  A számítástudomány matematikai alapjai, Nemzeti Tankönyvkiadó, Budapest, 1999.

Az ajánlott könyvek megtalálhatók a kari könyvtárban.	

VI. Az oktatói tevékenység heti tematikája
1. Formális nyelvtanok, nyelvek, alapfogalmak, Chomsky-féle nyelvosztályok
2. Normálalakok, kiterjesztett nyelvtanok
3. Véges automaták: nemdeterminisztikus, determiniosztikus, epszilon-lépéses v;ges automat’k
4. Véges automaták és reguláris nyelvek ekvivalenciája
5. determinisztikus véges automaták minimalizálása; pumpáló lemma reguláris nyelvekre
6. Reguláris kifejezések
7. Veremautomaták és környezetfüggetlen nyelvek
8. Pumpáló lemma környezetfüggetlen nyelvekre; környezetfüggetlen nyelvek normál alakjai 
9. Speciális nyelvtanok és nyelvek (LL(k) nyelvtanok, LR(k) nyelvtanok, elsőbbségi (precedencia) nyelvtanok)
10. Fordítóprogramok szerkezete, lexikális elemzés
11. Szintaktikai elemzésekl, LL(1) elemzés 
12. Szintaktikai elemzések, LR(1) elemzés
13. Szemantikai elemzések
14. 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-4. veremautomata ábrázolása és működése
5-6. lexikális elemző
7-10. alulról felfele elemző
11-13.  felülről lefele elemző	

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. Moldovan, G.: Limbaje formale si teoria automatelor, EduSoft, 2005.
7. Manna, Z., Programozáselmélet,  Műszaki Könyvkiadó, Budapest, 1981.
8. Moldovan, G., Cioban, V., Lupea, M, Limbaje formale si teoria automatelor. Culegere de probleme}, Editura Mesagerul, Cluj-Napoca,  1997.
      
Az ajánlott könyvek megtalálhatók a kari könyvtárban.	

	Dátum,						Az előadás felelőse,
	2009. okt.  1.					Dr. KÁSA Zoltán, egyetemi tanár