tematika2014

(szept. 8. hétfő): motiváció, véges automata definíciója, példák, reguláris nyelv definíciója, reguláris nyelvek zártak az unióra, metszetre, különbségre és komplementerre
(szeptemebr 12., péntek): hiányos, nemdetereminisztikus és epszilonos véges automata
(szeptember 15., hétfő): reguláris nyelvek zártsága a konkatenációra és a tranzitív lezártra; minimálautomata konstrukciója
(szeptember 22., hétfő): minimálautomata-konstrukció jóságának igazolása; pumpálási lemma reguláris nyelvekre; reguláris kifejezések definíciója
(szeptember 26., péntek): reguláris kifejezések és véges automaták ekvivalenciája; mese a Python nyelvtanáról, nyelvtan definíciója, példák

(szeptember 29., hétfő): Chomsky-hierarchia, nyelvtanok és nyelvek osztályozása; van nem generatív nyelv; reguláris nyelvek és reguláris nyelvtannal generálható nyelvek egyenértékűsége; jobb- és bal-reguláris nyelvtanok egyenértékűsége; algoritmikus kérdések reguláris nyelvekről: üresség, mindent tartalmaz, két nyelv megegyezik-e, beletartozás, a nyelv végtelen-e

(október 6., hétfő): CF nyelvtanok átalakításai: epszilon-szabályok és láncszabályok kiküszöbölése, felesleges szimbólumok elhagyása; CF nyelvtanok és nyelvek egyértelműsége

(október 13., hétfő): CF pumpálás, Ogden-féle pumpálás, CF nyelvek zártsági tulajdonságai
(október 18., szombat): CF nyelvekkel kapcsolatos algoritmikus kérdések; Állapottal elfogadó veremautomata, üres veremmel elfogadó veremautomata, ezek ekvivalenciája (egyik irány)

(október 20, hétfő): Üres veremmel elfogadó automatából állapottal elfogadó készítése; CF nyelvtanból veremautomata készítése, a másik irány bizonyítás nélkül; determinisztikus veremautomata, det CF nyelvek, det CF és CF nem ugyanaz

(november 3., hétfő): 1 szalagos, determinisztikus Turing gép, definíciók, példa: palindrómák nyelve; R és RE nyelvosztály definíciója, van RE-n kívüli nyelv; Church-Turing tézis R és RE-re vonatkozó része

(november 7., péntek): k-szalagos determinisztikus TG: definíció, példa a palindrómák elfogadására 2-szalgos géppel, minden k-szalagos szimulálható 1-szalagossal; nemdeterminisztikus TG, szimulálható determinisztikussal
(november 10., hétfő) kiszámolós TG, példák; TG kódolása 0-1 ábécé feletti szóvá; univerzális TG és ennek létezése; nevezetes nyelvek: diagonális nyelv nem rekurzívan felsorolható, univerzális nyelv RE-beli

(november 17., hétfő) univerzális nyelv nem rekurzív, megállási nyelv RE-beli, de nem rekurzív, L_{epsilon} RE-beli, de nem rekurzív; R és RE zártsági tulajdonságai: metszet, unió bizonyítva, konkatenált, tranzitív lezárt csak említve; komplementerre való zártság vizsgálata R és RE esetén: co R =R, R= RE metszet coRE

(november 24., hétfő) L_üres komplementere RE-beli, L_üres nem R-beli és nem RE-beli; T nemtriviális nyelvi tulajdonság definíciója, Rice tétel, példák rice tétel alkalmazására; Post megfeleltetési feladat (PCP), ez RE-beli, de nem rekurzív; CF nyelvtanok egyértelműsége nem dönthető el

(december 1., hétfő) CF nyelvtan egyértelműsége nem eldöntehtő; további eldönthetelenségi eredmények CF-ről: mindent generál-e, két nyelvtan ugyanazt generálja-e, két nyelvtan generál-e közös szót; Generatív nyelvtanok és TG-ek ekvivalenciája; Cs nyelvtanok és lineárisan korlátozott TG-ek ekvivalenciája;
(december 5., péntek) tár és időkorlátos Turing-gépek; DTIME, NTIME, DSPACE, NSPACE osztályok definíciója és alapvető tulajdonságai; P, NP, PSPACE, EXPTIME osztályok definíciója és alapvető tartalmazási eredmények; tár-idő tétel és következményei
(december 8., hétfő) Tár-idő tétel bizonyítása; Tanú-tétel (azaz az algeles és a nyau-s NP definíciók ekvivalansek); Karp-redukció, NP-teljesség, Cook-Levin tétel