Tematika (címszavakban)

2024 Ősz

1. Szept. 4.
   -- Ismétlés: ábécé, szó, nyelv.
   -- Véges automata és változatai: hiányos, nemdeterminisztikus.
   -- Új: epszilon-átmenetes véges automata.
   
   Szept. 5.
   -- 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
   
   
2. Szept. 11.
   -- A minimális automata és egyértelműsége. -- Minimalizálási algoritmus
   -- Példa minimalizálásra (táblázattal, máshogy)
   -- Minimalizálási algoritmus
   -- Példa minimalizálásra (táblázattal, máshogy)
   
   
3. Szept. 18.
   -- Reguláris kifejezések
   -- Reguláris kifejezések és reguláris nyelvek közötti kapcsolat
   -- Pumpálási lemma, példa
   
   Szept.19.
   -- Pumpálási lemma bizonyítása, további példák (ráadásként egy vers )
   -- Nyelvtanok
   
   
4. Szept. 25.
   -- Chomsky-hierarchia.
   -- Reguláris nyelvtanok.
   -- Reguláris nyelvtanok és reguláris nyelvek kapcsolata.
   -- CF nyelvtanok és epszilon-szabályok kiküszöbölése.
   
   
5. Okt. 2.
   -- Egyszeres szabályok kiküszöbölése
   -- Felesleges szimbólumok kiküszöbölése
   -- CF nyelvek zártak az unióra, konkatenálásra, tranzitív lezárásra.
   -- Veremautomaták ismétlés
   
   Okt. 3.
   -- Ü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)
   -- Környezetfüggetlen pumpálási lemma, példák
   -- Metszetre, komplementere nem zártak a CF nyelvek
   


6. Okt. 9.
   -- Levezetési fa - ismétlés.
   -- Környezetfüggetlen pumpálási lemma bironyítás
   -- Metszetre, komplementere nem zártak a CF nyelvek
   -- Beletartozás eldöntése CF nyelvre: van véges eljárás (elágázás és korlátozás)
   


7. Okt. 16.
   -- Chomsky-normálforma.
   -- A beletartozás eldöntése CF nyelvtan alapján: a CYK algoritmus.
   -- A beletartozás eldöntése reguláris nyelvekre
   
   Okt. 17.
   -- Konzultáció
   -- Algoritmikus kérdések reguláris nyelvekre: üresség, végesség, diszjunktság, egyenlőség.
   -- CF nyelvekre üresség, végesség eldöntése.
   -- Turing-gép ismétlés, Church-Turing-tézis.
   -- Rekurzív, rekurzívan felsorolható nyelvek.
   


8. ZH: okt. 21. 18 óra!
   
   Okt. 23. -- ünnep
   


9. Okt 30.
   -- pár szó a zh-ról
   -- Az R és RE osztály.
   -- Több szalagból egy szalag.
   -- Turing-gép determinizálás.
   -- Turing-gép kódja.
   -- A diagonális nyelv.
   -- Az univerzális nyelv.
   
   Okt. 31.
   -- az univerzális és a megállási nyelv.
   -- Komplemeter osztályok.
   -- R, RE, coRE kapcsolata.
   -- Rekurzív nyelvek zártsági tulajdonságai.
   


10. Nov 6.
    Reggel óra, este PÓTZH !!
    
    -- RE zártsági tulajdonságai.
    -- Az L_{epszilon}, L_{üreshalmaz} nyelv.
    -- Nem-triviális nyelvi tulajdonság. Rice-tétel, példák
    


11. Nov 13.
    -- Rice-tétel példa
    -- A dominóprobléma coRE-beli
    -- Post megfeleltetési problémája - példák
    -- CF nyelvtanok egyértelműsége algoritmikusan eldönthetetlen
    
    Nov.14.
    -- 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.
    -- Tár-idő tétel.
    


12. Nov. 20.
    -- Az idő- és tárosztályok tulajdonságai.
    -- P, NP, PSPACE, EXPTIME.
    -- A Chomsky 0. és 1. osztály kapcsolata a Turing-gépekkel.
    -- Moore-automaták.
    


13. Nov. 27.
    -- 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. 28.
    -- Véges fordító CF nyelvből CF nyelvet csinál.
    -- -- Veremfordító.
    -- Veremfordító és szintakszisvezérelt séma.
    -- Függvényt kiszámoló Turing-gép.
    


14. Dec.4.
    -- reggel óra, este ZH !!