Tematika (címszavakban)

2019 ősz

1. (szept. 9.) Ismétlés: Ábécé, szó, nyelv. Véges automata és változatai: hiányos, nemdeterminisztikus.
   Új: epszilon-átmenetes véges automata.
   Reguláris nyelvek, zártságuk a műveletekre (unió, metszet, különbség, komplementer).
   
   
2. (szept.16.) Még egyszer az epszilon-mentesítésről.
   A reguláris nyelvek zártak a konkatenálásra, tranzitív lezárásra.
   Állapotok ekvivalenciaosztályai, szavak ekvivalenciaosztályai.
   
   (szept.19.) DVA minimalizálása, a minimális automata egyértelműsége.
   Reguláris kifejezés, reguláris kifejezésből VA.
   
   
3. (szept.23.) Véges automatából reguláris kifejezés.
   Pumpálási lemma néhány példával.
   
   
4. (szept.30.) Kari szünet (Qpa)
   
   (okt.3.) Még egy kis pumpálás.
   Nyelvtanok, Chomsky-hierarchia.
   Reguláris nyelvtanok és reguláris nyelvek kapcsolata.
   CF nyelvtanok és epszilon-szabályok.
   
   
5. (okt.7.) CF nyelvtanokból egyszeres szabályok és felesleges szimbólumok elhagyása.
   A CF nyelvek zártak az unióra, konkatenálásra, tranzitív lezárásra.
   Rövid összefoglaló a levezetési fákról, egyértelműségről.
   
   
6.  (okt.14.) A környezetfüggetlen pumpálási lemma.
   Példa nem környezetfüggetlen nyelvre.
   Metszetre, különbségre nem zártak a CF nyelvek
   Veremautomata.
   
   (okt.17.) Üres veremmel elfogadó veremautomata.
   Determinisztikus CF nyelvek és zártsági tulajdonságaik.
   Veremautomaták és CF nyelvek kapcsolata.
   Algoritmikus kérdések reguláris nyelvekre: beletartozás, üresség, diszjunktság, egyenlőség, végesség.
   CF nyelvekre üresség, végesség eldöntése.
   
   
7.  (okt.21.) Chomsky-normálforma.
   A beletartozás eldöntése CF nyelvtan alapján: a CYK algoritmus.
   
   
8.  (okt.28.) Turing-gép: determinisztikus és nemdeterminisztikus, Church-Turing-tézis.
   Egy-szalagos TG.
   
   (okt.31.) Rekurzív, illetve rekurzívan felsorolható nyelvek.
   Az R és RE osztály, kapcsolatuk. R, RE zárt az unióra, metszetre, R a komplementer is. A diagonális, az univerzális és a megállási nyelv.
   
   
9.  (nov.4.) Az L_{epszilon}, L_{üreshalmaz} nyelv.
   Nem-triviális nyelvi tulajdonság. Rice-tétel
   
   
10.  (nov.11.) Rice-tétel bizonyításának befejezése, alkalmazások.
    A dominóprobléma.
    Post megfeleltetési problémája.
    
    (nov.14.) Eldönthetetlen problémák CF nyelvtanokra (egyértelműség, diszjunktság, teljesség, azonosság)
    A Chomsky 0. osztály kapcsolata a Turing-gépekkel.
    
    
11.  (nov.18.) Felsoroló Turing-gépek, RE- és R-beli nyelvek szavainak felsorolhatósága.
    Moore- és Mealy-automaták, ekvivalenciájuk.
    
    
12.  (nov.25.) Mealy-automata értékkészlete.
    Véges fordító fogalma, példák. Véges fordító reguláris nyelvből regulárisat, CF nyelvből CF nyelvet csinál.
    Veremfordító.
    
    (nov.28.) Veremfordító és szintakszisvezérelt séma.
    Jellemző nyelvtan és kapcsolata a fordítókkal.
    Függvényt kiszámoló Turing-gép.


13.  (dec.2.) Turing-gépek idő- és tárigénye, időkorlát, tárkorlát.
    Gyorsítási tételek, Hézag tétel.
    TIME és SPACE osztályok.
    Tár-idő tétel.
    P, NP, PSPACE, EXPTIME
    


14.  (dec.9.) Az 1. Chomsky-osztály és a nem csökkentő nyelvtanok ekvivalenciája;
    Az 1. osztálynak megfelelő automatatípus.
    Zártsági tulajdonságok.
    Közvetlen elérésű gép és kapcsolata a Turing-géppel.
    
    (dec.12.) Mese a Cerny-sejtésről, Kolmogorov-bonyolultságról, Busy beaverről.