Tematika (címszavakban)

2022 Ő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, konkatenálás).
   
2. Szept. 15.
   -- A reguláris nyelvek zártak a tranzitív lezárásra -- Állapotok ekvivalenciaosztályai, szavak ekvivalenciaosztályai.
   -- DVA minimalizálása, a minimális automata egyértelműsége.
   Szept. 16.
   -- Példa minimalizálásra (táblázattal, máshogy)
   -- Reguláris kifejezésből reguláris nyelv (VA)
   -- Reguláris nyelvből (DVA-ból) reguláris kifejezés
   
3. Szept. 23.
   -- Pumpálási lemma néhány példával. ( Versben )
   
   -- Nyelvtanok, Chomsky-hierarchia.
   
4. Szept. 29.
   -- Reguláris nyelvtanok és reguláris nyelvek kapcsolata.
   -- CF nyelvtanok és epszilon-szabályok kiküszöbölése.
   -- Egyszeres szabályok
   Szept. 30. QPA-szünet
   
5. Okt. 7.
   -- Egyszeres szabályok, felesleges szimbólumok
   -- CF nyelvek zártak az unióra, konkatenálásra, tranzitív lezárásra.
   -- Rövid összefoglaló levezetési fákról, egyértelműségről.
   
6. Okt. 13.
   -- Veremautomaták
   -- Üres veremmel elfogadó veremautomaták.
   -- Állapottal és üres veremmel elfogadás ekvivalenciája
   -- Pontosan a CF nyelvek az üres veremmel elfogadhatóak (csak az egyszerű irányt bizonyítottuk)
   -- Egy nem CF nyelv
   -- Metszetre, komplementere nem zártak a CF nyelvek.
   Okt. 14.
   -- konzultáció a zh-hoz
   -- Környezetfüggetlen pumpálási lemma
   


7. Okt.17. ZH1
   
   Okt. 21.
   -- Péda a CF pumpálásra
   -- Különbségre nem zártak a CF nyelvek
   -- Determinisztikus CF nyelvek zártsági tulajdonságai.
   -- Algoritmikus kérdések reguláris nyelvekre: beletartozás, üresség, végesség, diszjunktság, egyenlőség.
   -- CF nyelvekre üresség, végesség eldöntése.
   -- Chomsky-normálforma.
   
8. Okt. 27.
   -- A beletartozás eldöntése CF nyelvtan alapján: a CYK algoritmus.
   -- Turing-gép ismétlés, Church-Turing-tézis.
   -- Több szalagból egy szalag.
   -- Rekurzív, rekurzívan felsorolható nyelvek.
   -- Az R és RE osztály, kapcsolatuk.
   Okt. 28.
   -- Turing-gép determinizálás,
   -- A diagonális, az univerzális és a megállási nyelv.
   -- Komplemeter osztályok.
   
9. Nov.2. PZH1
   
   Nov. 4.
   -- Az L_{epszilon}, L_{üreshalmaz} nyelv.
   -- R, RE, coRE kapcsolata.
   -- R, RE zárt az unióra, metszetre, konkatenálásra, tranzitív lezártra, R a komplementerre is.
   
10. Nov. 10.
    -- Nem-triviális nyelvi tulajdonság. Rice-tétel
    -- Rice-tétel alkalmazásai Szept. 15.
    -- A dominóprobléma.
    -- Post megfeleltetési problémája.
    Nov. 11.
    -- Eldönthetetlen problémák CF nyelvtanokra (egyértelműség, diszjunktság, teljesség, azonosság)
    -- Turing-gépek idő- és tárigénye, időkorlát, tárkorlát.
    -- Gyorsítási tétel, Hierarchia tétel, Hézag tétel.
    -- TIME és SPACE osztályok.
    
11. Nov. 18.
    -- Tár-idő tétel.
    -- P, NP, PSPACE, EXPTIME
    -- A Chomsky 0. osztály kapcsolata a Turing-gépekkel.
    -- Az 1. osztálynak megfelelő automatatípus.
    -- Moore-automata
12. Nov. 24.
    -- Mealy-automata
    -- Kapcsolat a Moore- és Mealy automaták között
    -- Véges fordító
    -- Véges fordító reguláris nyelvből regulárisat csinál.
    
    Nov.25. -- szünet: Nyílt nap
13. Dec. 2.
    -- Véges fordító CF nyelvből CF nyelvet csinál.
    -- Veremfordító.
    -- Veremfordító és szintakszisvezérelt séma.
    -- Jellemző nyelvtan és kapcsolata a fordítókkal.
    -- Függvényt kiszámoló Turing-gép.
    
14. Dec.7. ZH2
    Dec. 8.
    -- Felsoroló Turing-gépek, RE- és R-beli nyelvek szavainak felsorolhatósága.
    -- Közvetlen elérésű gép és kapcsolata a Turing-géppel.
    Dec. 9.
    -- Mese a Cerny-sejtésről, Kolmogorov-bonyolultságról. -- Példa kiszámíthatalan függvényre: a buzgó mócsing (Busy beaver) probléma.
    
15. Dec.16. PZH2