NyAu tematika (címszavakban)

2021 ősz

1. hét
   szept. 9. (1.előadás)
   -- Ismétlés
   -- A véges automata korábbi (teljes, hiányos, determinisztikus, nemdetermnisztikus) -- eőszilon-átmenetes VA
   -- Reguláris nyelvek zártak az unió, konkatenálás, tranzitív lezárás műveletére
   
   szept.10. (2.előadás)
   -- Reguláris nyelvek zártak a metszetre, különbségre, komplementerre
   -- Állapotok ekvivalenciaosztályai, szavak ekvivalenciaosztályai
   -- DVA minimalizálása, a minimálautomata egyértelműsége
   
2. hét
   szept. 17. (3. előadás)
   -- Példa a minimalizálásra
   -- Reguláris kifejezések és reguláris nyelvek kapcsolata
   
3. hét
   szept. 23. (4. előadás)
   -- Nem regularitás bizonyítása - pumpálási lemma
   -- Példák a pumpálási lemma alkalmazására
   -- Nyelvtanok, Chomsky-hierarchia.
   
   szept. 24. (5. előadás)
   -- Majdnem reguláris nyelvtanok és reguláris nyelvtanok (epszilon-szabályok kiküszöbölése) -- Reguláris nyelvtanok és reguláris nyelvek kapcsolata
   -- CF nyelvtanok és majdnem CF nyelvtanok
   -- Egyszeres szabály fogalma, példa
   
4. hét
   okt.1. (6. előadás)
   -- Egyszeres szabályok, 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 emlékeztető
   -- Üres veremmel elfogadó veremautomata
   
5. hét
   okt.7. szünet (Qpa)
   okt.8. szünet (Qpa)
   
6. hét
   okt.15. (7. előadás)
   -- Állapottal és üres veremmel elfogadás ekvivalenciája
   -- A CF nyelvek az üres veremmel elfogadhatóak
   -- Környezetfüggetlen pumpálási lemma és alkalmazása
   
7. hét
   okt.18. ZH !
   
   okt.21. (8. előadás)
   -- A környezetfüggetlen pumpálási lemma további alkalmazásai
   -- CF nem zárt a metszetre, különbségre
   -- Determinisztikus CF nyelvek zártsági tulajdonságai
   -- Algoritmikus kérdések reguláris és CF nyelvekre: beletartozás, üresség, diszjunktság, egyenlőség, végesség.
   
   okt.22. (9. előadás)
   -- Beletartozás CF nyelvekre: az elágazás-és-korlátozás technika exponenciális algoritmust ad
   -- Chomsky-normálforma
   -- CF nyelvtanok átalakítása Chomsky-normálformára
   -- CYK algoritmus
   -- Turing-gép felelevenítése
8. hét
   okt.29. (10. előadás)
   -- Determinisztikus és nemdeterminisztikus TG
   -- Church-Turing-tézis.
   -- Egy szalagos TG.
   -- Rekurzív, rekurzívan felsorolható nyelvek.
   -- Az R és RE osztály, kapcsolatuk.
   -- A diagonális nyelv nincs RE-ben.
   -- Az univerzális nyelv (RE-R)-ben van.
   
9. hét
   nov.4. (11. előadás)
   -- A megállási nyelv (RE-R)-ben van.
   -- Néhány továábi nyelv (L_epszilon, L_üres).
   -- Komplemeter osztályok.
   -- R, RE, coRE kapcsolata.
   -- R, RE zárt az unióra, metszetre, konkatenálásra, tranzitív lezártra, R a komplementerre is.
   
   nov.5. (12. előadás)
   -- Nem-triviális nyelvi tulajdonság.
   -- Rice-tétel és alkalmazásai.
   -- Dominóprobléma.
   
10. hét
    nov. 12. (13. előadás)
    -- A dominóprobléma nyelve coRE-beli.
    -- Post megfeleltetési problémája.
    -- Eldönthetetlen problémák CF nyelvtanokra.
    
11. hét
    nov. 18. (14. előadás)
    -- A Chomsky 0. és 1. osztály kapcsolata a Turing-gépekkel.
    -- Moore- és Mealy-automaták.
    
    nov. 19. (15. előadás)
    -- Véges fordító, véges fordítás
    -- Véges fordítás reguláris nyelvből regulárisat, CF-ből CF-et csinál
    -- Veremfordító.
    -- Szintakszisvezérelt fordítási séma.
    
12. hét
    nov. 26. szünet (Nyílt nap)
    
13. hét
    dec. 2. (16. előadás)
    -- Veremfordító és szintakszisvezérelt fordítási séma kapcsolata.
    -- Jellemző nyelvtan és kapcsolata a fordítókkal.
    -- Függvényt kiszámoló Turing-gép.
    -- Turing-gépek idő- és tárigénye, időkorlát, tárkorlát.
    -- TIME és SPACE osztályok.
    -- Tár-idő tétel
    
    dec. 3. (17. előadás)
    -- További kapcsolatok az osztályok között
    -- P, NP, PSPACE, EXP
    .. Karp-redukció
    -- NP-teljesség, PSPACE-teljesség, példák
14. hét
    dec.9. ZH !
    

Következő előadáson várható:

dec. 10.

-- ?? (valami lesz!)