Tematika (címszavakban)

2020 ősz

1. szept. 11. (1.előadás)
   -- Ismétlés: ábécé, szó, nyelv.  Véges automata és változatai: hiányos, nemdeterminisztikus.
   -- epszilon-átmenetes véges automata.
   -- Reguláris nyelvek, zártságuk a műveletekre (unió, metszet, különbség, komplementer, konkatenálás, tranzitív lezárt).
2. hét: szept.17. (2.előadás)
   -- Állapotok ekvivalenciaosztályai, szavak ekvivalenciaosztályai.
   -- DVA minimalizálása, a minimális automata egyértelműsége.
   -- Reguláris kifejezés, reguláris kifejezésből VA.
   szept.18. (3.előadás)
   -- VA-ból reguláris kifejezés.
   -- Pumpálási lemma néhány példával.
   
3. hét: szept.25. (4.előadás)
   -- Nyelvtanok, Chomsky-hierarchia.
   -- Reguláris nyelvtanok és reguláris nyelvek kapcsolata.
   -- CF nyelvtanok és epszilon-szabályok, egyszeres szabályok
   
4. hét: okt.1. (5.előadás)
   -- felesleges szimbólumok
   -- CF nyelvek zártak az unióra, konkatenálásra, tranzitív lezárásra.
   -- Összefoglaló levezetési fákról, egyértelműségről, veremautomatákról.
   okt.2. (6.előadás)
   -- Üres veremmel elfogadó veremautomata és a CF nyelvek.
   -- Környezetüggetlen pumpálási lemma.
   -- Példák nem környezetfüggetlen nyelvre.
   
5. hét: okt.9. (7.előadás)
   -- Metszetre, különbségre nem zártak a CF nyelvek
   -- Determinisztikus CF nyelvek és zártsági tulajdonságaik.
   -- 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.
   -- Chomsky-normálforma.
   
6. hét: okt.15. (8.előadás)
   -- CYK algoritmus.
   okt.16. (9.előadás)
   -- Turing-gép ismétlés: determinisztikus és nemdeterminisztikus, Church-Turing-tézis.
   -- Egy szalagos TG.
   -- Az R és RE osztályok -- Diagonális, univerzális megállási nyelv. Univerzális Turing-gép
7. hét: okt.23. szünet
   De előtte: okt.20. zh az 1-8 előadások anyagából
8. hét: okt.29. (10.előadás)
   -- Az R és RE osztályok viszonya, zártsági tulajdonságaik -- További nem rekurzív nyelvek
   -- Rice-tétel, példák
   okt. 30. (11. előadás)
   -- Rice-tétel bizonyítás
   -- Alkalmazások
   -- A dominóprobléma.
   -- Post megfeleltetési problémája.
   -- CF nyelvtanok egyértelműsége algoritmikusan eldönthetetlen
9. hét: nov.6. (12.előadás)
   -- További eldönthetetlen problémák CF nyelvtanokra ( diszjunktság, teljesség, azonosság)
   -- A Chomsky 0. osztály kapcsolata a Turing-gépekkel.
   -- Felsoroló Turing-gépek, RE- és R-beli nyelvek
   -- Moore-automa
10. hét: nov.12. szünet (TDK)
    nov.13. rektori szünet
    
11. hét: nov.20. (13.előadás)
    -- Mealy-automaták, kapcsolat a Moore-automatákkal.
    -- Véges fordító fogalma, példák, tulajdonságok.
12. hét: nov.26. (14.előadás)
    -- 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.
    -- Turing-gépek idő- és tárigénye, időkorlát, tárkorlát.
    nov.27. szünet (nyílt nap)
    
13. hét: dec.4. (15.előadás)
    -- TIME és SPACE osztályok.
    -- Tár-idő tétel.
    -- P, NP, PSPACE, EXPTIME
    

Következő előadáson -- dec.10. (16.előadás) -- várható:
-- P, NP, NP-teljesség
-- PSPACE, PSPACE-teljesség
-- P, NP, PSPACE, EXPTIME
-- Közvetlen elérésű gép és kapcsolata a Turing-géppel.
dec.10. este ZH !!