Az előadások anyaga

1. előadás

Alapdefiníciók, nyelvtan definíciója, hierarchia a nyelvosztályok között, megszámlálhatóan végtelen sok generatív nyelv van, algoritmus a nyelvbe tartozás eldöntésére az 1-es nyelvosztály esetén, véges automata definíciója, működése, az elfogadás feltétele

2. előadás

Determinizálás: hogyan kell egy tetszőleges VA-t determinisztikus VA-vá alakítani; További VA átalakítások: teljesen specifikálás, egy végállapot legyen, amiből nem megy ki nyíl, egy kezdőállapot legyen, amibe nem megy be nyíl, epszilon-átmenetek kiküszöbölése; VA-k és jobbreguláris nyelvtanok ekvivalenciája; VA-k és balreguláris nyelvtanok ekvivalenciája; A minimálautomata megszerkesztésének algoritmusa

3. előadás

Elmaradt a nyílt nap miatt

4. előadás

A minimálautomata unicitásának bizonyítása; kétirányú véges automaták; reguláris kifejezések, reguláris halmazok definíciója; reguláris kifejezésekhez lehet VA-t adni (ez még nincs teljesen befejezve)

5. előadás

Reguláris kifejezések: minden reguláris kifejezés által meghatározott nyelv reguláris és fordítva, azaz, minden reguláris nyelvhez adható reguláris kifejezés; Reguláris nyelvek zártsága a műveletekre; Pumpálási lemma reguláris nyelvekre; CF nyelvtanoknál a levezetési fa, bal és jobb levezetés definíciója; egyértelmű és nem egyértelmű nyelvtanok és nyelvek; Kicsi mese a fordításról

6. előadás

CF nyelvtanok átalakításai: epszilon-szabályok kiküszöbölése, lánc szabályok kiküszöbölése, felesleges szimbólumok kiküszöbölése. Chomsky normál forma; közvetlen balrekurzivítás kiküszöbölése

7. előadás

Greibach normál forma; Veremautomata definíciója, elfogadás üres veremmel és állapottal, ezek egyenértékűsége; Rönthgenszemű veremautomata

8. előadás

Veremautomaták és CF nyelvtanok egyenértékűsége; Pumpálási lemma CF nyelvekre, Determinisztikus CF nyelvek, Zártsági tulajdonságok CF és det CF nyelvekre (CF zárt: unió, tranzitív lezárt, konkatenált, nem zárt: metszet, komplementer; det CF zárt: komplementer, nem zárt: metszet és únió)

9. előadás

Reguláris és CF nyelvek metszete CF; Fordítás fogalma; Véges fordító; Reguláris és CF nyelvek zártsága a véges fordításra; Egyszerű szintaxis vezérelt fordítási séma; Veremfordító; Az ESZFS és a veremfordító egyenértékűsége

10. előadás

Jellemző nyelvtanok, szigorúan jellemző nyelvtanok; Elemzőkról általában; Earley algoritmus

11. előadás

LL(k) elemzés

12. előadás

LR(k) elemzés

13. előadás

Precedencia elemzés, erős és gyenge is

14. előadás

Operátor precedencia elemzés, mese a különböző elemzők erejéről és a fordítókról,