Tematika (címszavakban)

2015 ősz

   (Az első zh anyaga lilával,  a második zh anyaga zölddel, az utolsó zh anyaga kékkel kiemelve.)

1. (szept. 7. hétfő): Követelmények; Motiváció; Véges automata definíciója, reguláris nyelv definíciója, reguláris nyelvek zártak unióra, metszetre, különbségre
   
2. (szeptember 10., csütörtök): Reguláris nyelvek zártak a komplementerre; Hiányos, nemdetereminisztikus és epszilonos véges automata
3. (szeptember 14., hétfő): Reguláris nyelvek zártsága a konkatenálásra és tranzitív lezártra; Minimálautomata elve és konstrukciója
4. (szeptember 21., hétfő): Minimálautomata konstrukciója jó, a minimálautomata egyértelmű; Pumpálási lemma reguláris nyelvekre; Reguláris kifejezések definíciója
5. (szeptember 24., csütörtök): Reguláris kifejezésekkel leírható nyelvek = reguláris nyelvek; Motiváció a nyelvtanokra (Python), a nyelvtan definíciója, példák; Mese Chomsky-ról és a természetes nyelvekről
6. (szeptember 28., hétfő): Chomsky-hierarchia, nyelvosztályok (REG, CF, CS, generatív); Reguláris nyelvtanok és véges automaták egyenértékűek; Jobb- és balreguláris nyelvtanok egyenértékűek; Eldöntési kérdések reguláris nyelvekről: üres-e, véges-e, adott szó benne van-e, két nyelv metszete üres-e, két nyelv ugyanaz-e.
7. (október 5., hétfő): CF nyelvtanok, CF nyelvtanok átalakításai (epszilon-mentesítés, láncszabályok kiirtása, felesleges szimbólumok eltüntetése); Pumpálási lemma CF nyelvekre (a lemma kimondása és két példa);
   
8. (október 12., hétfő): CF pumpálási lemma bizonyítása; Ogden-féle pumpálási lemma (bizonyítás nélkül), példa; CF nyelvek zártsági tulajdonságai; CF nyelvekkel kapcsolatos eldöntési kérdések;
   
9. (október 19., hétfő): Veremautomata, állapottal és üres veremmel való elfogadó automaták, ezek egyenértékűsége
10. (október 22., csütörtök): CF nyelvtanból veremautomata készítése, mese az LL(k) elemzőkről; Veremautomatából CF nyelvtan készítése (csak maga az állítás, hogy lehetséges, a konstrukció nem volt); Determinisztikus veremautomata, példa, a det CF nyelvek zártsági tulajdonságai: komplementerre igen (a konstrukció elve csak, pontos bizonyítás nem volt), metszetre nem (bizonyítással), unióra nem (bizonyítással); A Chomsky normálforma definíciója
    
11. (október 26., hétfő): Chomsky Normálforma CF nyelvtanokra, átalakítás CNF-ra; Cocke-Younger-Kasami algoritmus, a levezetési fák visszakövetése is; Egyértelműség CF nyelvtanok és nyelvek esetén
12. (november 2., hétfő) 1-szalagos, determinisztikus, nyelvet felismerő Turing-gép definíciója; Példák: palindrómák részletesen; R és RE nyelvosztályok definíciója
13. (november 5., csütörtök) Church-Turing tézis; k-szalagos determinisztikus Turing-gép, palindrónás példa, elvivalencia az egyszalagossal; nemdeterminisztikus Turing-gép, ekvivalencia a determinisztikussal
14. (november 9., hétfő) kiszámolós TG-ek; TG-ek kódolása, univerzális TG; nevezetes nyelvek: diagonális nyelv nem rekurzívan felsorolható
15. (november 16., hétfő) univerzális nyelv, megállási nyelv és L_epszilon rekurzívan felsorolhatók, de nem rekurzívak; R és Re zárt unióra, metszetre; coX definíciója és tulajdonságai, coR = R, R = RE metszet coRE
16. (november 19., csütörtök) L_üres rekurzívan felsorolható (diagonális eljárás), L_üres nem rekurzív; Rice-tétel, bizonyítás, példák a Rice-tétel alkalmazására
17. (november 23., hétfő) PCP probléma, kapcsolata a CF nyelvtanok egyértelműségével; CF nyelvtanokkal kapcsolatos algoritmikus kérdések;  Nyelvtanok és TG-ek kapcsolata,  
    
18. (november 30, hétfő) CS nyelvtanok és lineárisan korlátozott TG-ek kapcsolata; Tár- és időkorlát determinisztikus és nemdeterminisztikus TG-ekre; TIME, NTIME, SPACE és NSPACE nyelvosztályok; P, NP, PSPACE, EXPTIME osztályok és kapcsolatuk 
19. (december 3., csütörtök) Tár-idő tétel bizonyításe és következményei; Algel-es és Nyau-s NP definíció ugyanaz: tanú-tétel
20. (december 7., hétfő) Karp-redukció, Cook-Levin tétel, 3-SAT NP teljes, 3-SZÍN NP-teljes