Tematika (címszavakban)

2023 Ősz

1. Szept. 6.
   -- Ismétlés: ábécé, szó, nyelv.
   -- Véges automata és változatai: hiányos, nemdeterminisztikus.
   -- Új: epszilon-átmenetes véges automata.
   
   Szept. 7.
   -- Reguláris nyelvek, zártságuk a műveletekre (unió, metszet, különbség, komplementer.
   -- A reguláris nyelvek zártak a konkatenálásra és a tranzitív lezárásra
   -- Állapotok ekvivalenciaosztályai, szavak ekvivalenciaosztályai, ezek kapcsolata.
   -- A minimális automata egyértelműsége.
   
   
2. Szept. 13.
   -- Minimalizálási algoritmus
   -- Példa minimalizálásra (táblázattal, máshogy)
   -- Reguláris kifejezések
   
   
3. Szept. 20.
   -- Reguláris kifejezések és reguláris nyelvek közötti kapcsolat
   -- Pumpálási lemma
   
   Szept.21.
   -- Pumpálásra példák ( Versben )
   -- Nyelvtanok, Chomsky-hierarchia.
   -- Reguláris nyelvtanok.
   
   
4. Szept. 27.
   -- Reguláris nyelvtanok és reguláris nyelvek kapcsolata.
   -- CF nyelvtanok és epszilon-szabályok kiküszöbölése.
   -- Egyszeres szabályok kiküszöbölése
   -- Felesleges szimbólumok kiküszöbölése
   
   
5. Okt. 4.
   -- CF nyelvek zártak az unióra, konkatenálásra, tranzitív lezárásra.
   -- Veremautomaták ismétlés
   -- Ü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)
   
   Okt. 5.
   -- Levezetési fák, egyértelműség - ismétlés.
   -- Környezetfüggetlen pumpálási lemma, példák
   -- Metszetre, komplementere nem zártak a CF nyelvek
   -- Algoritmikus kérdések
   


6. Okt. 11.
   -- 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.
   


7. Okt. 18.
   -- A beletartozás eldöntése CF nyelvtan alapján: a CYK algoritmus.
   -- Turing-gép ismétlés, Church-Turing-tézis.
   -- Rekurzív, rekurzívan felsorolható nyelvek.
   -- Az R és RE osztály.
   
   Okt. 19.
   -- Több szalagból egy szalag.
   -- Turing-gép determinizálás.
   -- Turing-gép kódja.
   -- A diagonális nyelv.
   


8. Okt. 25.
   -- Konzultáció
   -- Az univerzális és a megállási nyelv.
   -- Komplemeter osztályok.
   -- Rekurzív nyelv komplementere rekurzív.
   -- Ha a nyelv és komplemetere is rek. felsorolható, akkor a nyelv rekurzív.
   
   ZH: okt. 25. 18 óra!


9. Nov 1. -- szünet
   
   Nov 2.
   -- Komplemeter osztályok.
   -- R, RE, coRE kapcsolata.
   -- R, RE zártsági tulajdonságai.
   -- Az L_{epszilon}, L_{üreshalmaz} nyelv.
   -- Nem-triviális nyelvi tulajdonság. Rice-tétel
   


10. Nov 8.
    -- Rice-tétel bizonyítás
    -- Rice-tétel alkalmazásai
    -- A dominóprobléma coRE-beli
    -- Post megfeleltetési problémája - példák
    
    este PZH1 !


11. Nov 15.
    -- 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.
    -- TIME és SPACE osztályok.
    -- A Chomsky 0. osztály kapcsolata a Turing-gépekkel.
    -- Az 1. osztálynak megfelelő automatatípus.
    
    Nov.16. -- szünet (TDK)


12. Nov. 22.
    -- Tár-idő tétel.
    -- P, NP, PSPACE, EXPTIME
    -- Moore-automata
    


13. Nov. 29.
    -- 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.30.