Tematika (címszavakban)

2013 õsz

1. (szept. 9. hétfő): motiváció, alapdefiníciók (ábécé, szó, nyelv), véges automata, reguláris nyelvek, ezek zártsága az unióra, metszetre, különbségre és komplementerre
2. (szeptember 13., péntek): hiányos véges automata, nemdeterminisztikus véges automata, epszilon-átmenetes (nem determinisztikus) véges automata
3. (szeptember 16., hétfő): sportnap miatt elmarad
4. (szeptember 23., hétfő): konkatenálásra és tranzitív lezártra való zártság; minimálautomata
5. (szeptember 27., péntek): minimálautomata egyértelműsége; pumpálási lemma reguláris nyelvekre; reguláris kifejezések definíciója, a reguláris kifejezésekre van véges automata 
6. (szeptember 30., hétfő): VA-hoz van reguláris kifejezés; mese a Python nyelvtanáról, generatív nyelvtan definíciója, példák; nyelvtanok és nyelvek osztályozása: generatív, CS, CF, reguláris; van nem generatív nyelv
7. (október 7. hétfő): reguláris nyelvtanok és véges automaták egyenértékűsége; bal- és jobb-reguláris nyelvtanok egyenértékűsége; algoritmikus kérdések reguláris nyelvekről: beletartozás, két nyelv egyenlősége, két nyelv metszete üres-e, nyelv üres-e, nyelv végtelen-e; CF nyelvtanok átalakításai: epszilon-szabályok kiirtása 
8. (október 11., péntek): Qpa miatt elmarad
9. (október 14., hétfő): láncszabályok és felesleges szimbólumok kiirtása; levezetési fa, egyértelműség: aritmetikai kifejezések nyelvtana, if-then-else példa
10. (október 21., hétfő): pumpálási lemma CF nyelvekre, Ogden-féle pumpálási lemma (bizonyítás nélkül); CF nyelvek zártsági tulajdonságai (unió, konkatenált, tranzitív lezártra igen, metszet, komplementer, különbségre nem); CF nyelvtannal adott nyelv ürességének eldöntése
11. (október 25., péntek): CF nyelvek további algoritmikus kérdései; Chomsky normálforma, Cocke-Younger-Kasami algoritmus
12. (október 28, hétfő): veremautomata definíciója (állapottal elfogadó, nemdeterminisztikus), üres veremmel elfogadó veremautomata definíciója, az állapottal és az üres veremmel elfogadó veremautomaták ekvivalenciája
13. (november 4., hétfő): veremautomaták és CF nyelvtanok ekvivalenciája (a PDA-ból nyelvtan irány bizonyítás nélkül); determinisztikus veremautomata, det CF nyelvek, det CF nyelvek zártsági tulajdonságai (zárt a komplementerre, de nem zárt metszetre és unióra);
    mese az elemzőkről
14. (november 8., péntek) Turing-gép definíciója, elfogadás feltétele, elfogadott nyelv definíciója; példa: palindromákra TG, a^nb^nc^n nyelvre TG vázlata; rekurzív és rekurzívan felsorolható nyelvek, R és RE nyelvosztály
15. (november 11., hétfő) k-szalagos Turing-gép, példa: palindromák elfogadása 2-szalgossal, k-szalagos és 1-szalagos gép ekvivalenciája; nemdeterminisztikus TG definíciója, ekvivalenciája a determinisztikussal
16. (november 18., hétfő) számoló Turing-gép, erre vonatkozó Church-Turing-tézis; Turing-gépek kódolása, univerzális Turing-gép; diagonális nyelv, univerzális nyelv, megállási nyelv (bizonyítások nélkül most még)
17. (november 25., hétfő) megállási nyelv, L_epszilon; R és RE zártsági tulajdonságai: metszet, unió (ezek bizonyítással is), konkatenált, tranzitív lezárt (ez utóbbi kettő csak kimondva); coX és tulajdonságai, R= coR, R = RE metszet coRE
18. (december 2., hétfő) L_empty; Rice-tétel és következményei; PCP, eldönthetetlen tulajdonságok CF nyelvtanokról: egyértelműség
19. (december 6., péntek) eldönthetetlen tulajdonságok CF nyelvtanokról (bizonyítás nélkül): egyenlőség, metszet nem-üres, mindent generál; eldönthető kérdések CF nyelvtanokról (ismétlés): üresség, végesség, szó tartalmazása; nyelvtanok és TG-ek kapcsolata (vázlatosan), CS nyelvtanok és lineárisan korlátozott TG-ek kapcsolata (biz nélkül); tár és időkorlátos TG-ek, TIME, SPACE, NTIME, NSPACE nyelvosztályok definíciója, ezek alapvető tulajdonságai; P, NP, PSPACE, EXPTIME nyelvosztályok definíciója, P része NP-nek
20. (december 9., hétfő) tár-idő tétel és következményei: P, PSPACE és EXPTIME kapcsolata; NP mostani és algeles definíciója ugyanaz: tanú-tétel; Karp-redukció, NP-teljesség, Cook-Levin tétel;