Tematika (címszavakban)
2022 Ősz
- Szept. 9.
-- Ismétlés: ábécé, szó, nyelv.
-- Véges automata és változatai: hiányos, nemdeterminisztikus.
-- Új: epszilon-átmenetes véges automata.
-- Reguláris nyelvek, zártságuk a műveletekre (unió, metszet,
különbség, komplementer, konkatenálás).
- Szept. 15.
-- A reguláris nyelvek zártak a tranzitív lezárásra
-- Állapotok ekvivalenciaosztályai, szavak ekvivalenciaosztályai.
-- DVA minimalizálása, a minimális automata egyértelműsége.
Szept. 16.
-- Példa minimalizálásra (táblázattal, máshogy)
-- Reguláris kifejezésből reguláris nyelv (VA)
-- Reguláris nyelvből (DVA-ból) reguláris kifejezés
- Szept. 23.
-- Pumpálási lemma néhány példával. ( Versben )
-- Nyelvtanok, Chomsky-hierarchia.
-
Szept. 29.
-- Reguláris nyelvtanok és reguláris nyelvek kapcsolata.
-- CF nyelvtanok és epszilon-szabályok kiküszöbölése.
-- Egyszeres szabályok
Szept. 30. QPA-szünet
-
Okt. 7.
-- Egyszeres szabályok, felesleges szimbólumok
-- CF nyelvek zártak az unióra, konkatenálásra, tranzitív
lezárásra.
-- Rövid összefoglaló levezetési fákról, egyértelműségről.
- Okt. 13.
-- Veremautomaták
-- Ü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)
-- Egy nem CF nyelv
-- Metszetre, komplementere nem zártak a CF nyelvek.
Okt. 14.
-- konzultáció a zh-hoz
-- Környezetfüggetlen pumpálási lemma
-
Okt.17. ZH1
Okt. 21.
-- Péda a CF pumpálásra
-- Különbségre nem zártak a CF nyelvek
-- Determinisztikus CF nyelvek zártsági tulajdonságai.
-- 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.
- Okt. 27.
-- A beletartozás eldöntése CF nyelvtan alapján: a CYK algoritmus.
-- Turing-gép ismétlés, Church-Turing-tézis.
-- Több szalagból egy szalag.
-- Rekurzív, rekurzívan felsorolható nyelvek.
-- Az R és RE osztály, kapcsolatuk.
Okt. 28.
-- Turing-gép determinizálás,
-- A diagonális, az univerzális és a megállási nyelv.
-- Komplemeter osztályok.
-
Nov.2. PZH1
Nov. 4.
-- Az L_{epszilon}, L_{üreshalmaz} nyelv.
-- R, RE, coRE kapcsolata.
-- R, RE zárt az unióra, metszetre, konkatenálásra, tranzitív lezártra, R a komplementerre is.
- Nov. 10.
-- Nem-triviális nyelvi tulajdonság. Rice-tétel
-- Rice-tétel alkalmazásai Szept. 15.
-- A dominóprobléma.
-- Post megfeleltetési problémája.
Nov. 11.
-- 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.
-- Gyorsítási tétel, Hierarchia tétel, Hézag tétel.
-- TIME és SPACE osztályok.
-
Nov. 18.
-- Tár-idő tétel.
-- P, NP, PSPACE, EXPTIME
-- A Chomsky 0. osztály kapcsolata a Turing-gépekkel.
-- Az 1. osztálynak megfelelő automatatípus.
-- Moore-automata
-
Nov. 24.
-- 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.25. -- szünet: Nyílt nap
-
Dec. 2.
-- Véges fordító CF nyelvből CF nyelvet csinál.
-- 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.
-
Dec.7. ZH2
Dec. 8.
-- Felsoroló Turing-gépek, RE- és R-beli nyelvek
szavainak felsorolhatósága.
-- Közvetlen elérésű gép és kapcsolata a Turing-géppel.
Dec. 9.
-- Mese a Cerny-sejtésről, Kolmogorov-bonyolultságról.
-- Példa kiszámíthatalan függvényre: a buzgó mócsing (Busy beaver) probléma.
-
Dec.16. PZH2
Következő előadáson várható