Tematika (címszavakban)

2018 ősz

  1. (szept. 4.): Ábécé, szó, nyelv. Véges automata és változatai: hiányos, nemdeterminisztikus, epszilon-átmenetes

    (szept.6.): Reguláris nyelvek, zártságuk a műveletekre (unió, metszet, különbség, konkatenált, tranzitív lezárt).
    Szavak egy nyelvre vonatkozó ekvivalenciája, a reláció tulajdonságai. Reguláris nyelv minimálautomatája az ekvivalenciarelációkon, mint állapotokon

  2. (szept 11.): Minimalizálás. Reguláris kifejezések. A reguláris kifejezések által leírt nyelvek regulárisak.

  3. (szept. 18): Véges automatából reguláris kifejezés. Pumpálási lemma néhány példával.

    (szept. 20): szünet -- Sportnap

  4. (szept. 25): Nyelvtanok, Chomsky-hierarchia; Reguláris nyelvtanok és reguláris nyelvek kapcsolata; CF nyelvtanok és epszilon-szabályok.


  5. (okt, 2): CF nyelvtanokból egyszeres szabályok és felesleges szimbólumok elhagyása. A CF nyelvek zártak az unióra, konkatenálásra és tranzitív lezáráse. A környezetfüggetlen pumpálási lemma, példa nem környezetfüggetlen nyelvre.

    (okt. 4): CF pumpálási lemma bizonyítása. Veremautomata. Determinisztikus CF nyelvek és zártásgi tulajdonságaik. Üres veremmel elfogadó veremautomata.


  6. (okt. 9): Üres veremmel pontosan a CF nyelveket lehet elfogadni.
    7. CF nyelvtanból üres veremmel elfogadó veremautomata. Algoritmikus kérdések reguláris nyelvekre (beletartozás, üresség, azonosság, diszjunktság, végesség). A beletartozás eldöntése CF nyelvtan alapján: van véges algoritmus. A CYK algoritmus
     
    (okt.13) Szombat !! : Chomsky-normálformára hozás. Turing-gépek, Church-Turing-tézis. Több szalagból egy szalag, nemdeterminisztikusból determinisztikus. Rekurzív, illetve rekurzívan felsorolható nyelvek. Az R és RE osztály.

  7. (okt. 16): R, RE, coRE kapcsolata, R, RE zártsági tulajdonságai. A diagonális nyelv nincs RE-ben. Univerzális Turing-gép. Az univerzális és a megállási nyelv (RE-R)-ben van.

    (okt. 18):  Az L_{epszilon} nyelv  (RE-R)-ben van. Az L_{üreshalmaz} nyelv co RE-beli. Nem-triviális nyelvi tulajdonság. A Rice-tétel kimondása és alkalmazásai.

  8. (okt. 23): ünnep

  9. (okt.30): Rice-tétel bizonyítása, alkalmazások. A dominóprobléma, a hozzá tartozó D nyelv coRE-ben van, de nincs R-ben. Post megfeleltetési problémája, példák.

    (nov. 1): ünnep

  10. (nov. 6): PCP nyelv RE-beli, de nem rekurzív. CF nyelvtanok egyértelműsége algoritmikusan nem eldönthető. Turing-gép elfogadó számításai és a CF nyelvek kapcsolata. Üresség, azonosság, teljesség eldönthetetlen a CF nyelvekre.

  11. (nov.13.): Felsoroló Turing-gépek, RE- és R-beli nyelvek szavainak felsorolhatósága. A Chomsky 0. oszt kapcsolata a Turing-gépekkel. Az 1. osztálynak megfelelő automata típus. Az osztályok zártsági tulajdonságai. Moore-automaták.

    (nov.15): Mealy-automaták. Ekvivalenciájuk a Moore-automatákkal. Mealy-automata értékkészlete reguláris nyelv. Véges fordító. Véges fordító reguláris nyelvből reguláris nyelvet állít elő.

  12. (nov.20.): Véges fordító CF nyelvből CF nyelvet állít elő. Veremfordító és szintakszisvezérelt séma. Jellemző nyelvtan és kapcsolata a fordítókkal. Függvényt kiszámoló Turing-gép.

  13. (nov.27): Turing-gépek idő- és tárigénye, időkorlát, tárkorlát. Gyorsítási tételek, Hézag tétel. TIME és SPACE osztályok, tulajdonságaik. P, NP, PSPACE, EXPTIME. Tár-idő tétel és következményei.

    (nov.29):  A legfontosabb osztályok közötti kapcsolatok. Példák NP-teljes és PSPACE-teljes nyelvekre.  Közvetlen elérésű gép és kapcsolata a Turing-géppel.

  14. (dec. 4): Mese a Cerny-sejtésről, Kolmogorov-bonyolultságról, Busy-beaverről.