Formális nyelvek és automaták tematika, 2016/17 őszi félév

1. A formális nyelvek elméletének történeti gyökerei (természetes nyelvek leírása, programozási nyelvek szintaxisának leírása, BNF, EBNF, szintaxis gráfok).

2. A formális nyelvek elméletének alapfogalmai (ábécé, szó, nyelv, nyelvcsalád), műveletek ábécéken, szavakon (megfordítás, hossz, relatív hossz, konkatenálás, homomorfizmus), nyelveken (halmazműveletek, megfordítás, konkatenálás, lezárás), tulajdonságaik. Betű-ekvivalens nyelvek, univerzális ábécé.

3. Formális nyelvek néhány alkalmazása (programnyelvi struktúrák, teknőc grafika, vörös algák, Hamilton gráfok)

4. Nyelvek megadásának konstruktív módszerei (egyszerű listázás, felsoroló, parciálisan eldöntő, illetve totálisan eldöntő algoritmusok, logikai kifejezések, műveletek, matematikai gépek, formális nyelvtanokkal), példák.

5. A generatív nyelvtan felépítése, a közvetlen és közvetett levezetés, a nyelvtan által generált nyelv, példák, a nyelvtani alaptípusok definíciója (a jegyzetben ezek a kiterjesztett típusok), az általuk meghatározott nyelvi osztályok, példák adott típusú nyelvtanokra.

6. Megszorított típusok, (a jegyzetben ezek az alapdefiníciók), normálformák. A megszorítási és normálforma tételek, bizonyításuk a 2. és 3. típus esetében nyelvtani konstrukciókkal (epszilon-mentesítés, láncmentesítés, hosszredukció).

7. A nyelvek Chomsky - féle gyenge és erős hierarchiája. A nyelvtannal való leírás korlátai (bizonyítással), Church - tézis.

8. A Chomsky féle nyelvosztályok és a reguláris műveletek kapcsolata (konstrukciók csak a 2. és 3. típusra).

9. A szóprobléma. A szóprobléma megoldása 0. és 1. típusú nyelvek esetén az összes levezetést reprezentáló fa szintfolytonos bejárásával, a gyakorlati felhasználás korlátai (0. típus esetén parciálisan rekurzív az algoritmus, 1. típus esetén rekurzív az algoritmus, de futási ideje a szó hosszában exponenciális).

10. Véges automaták, determinisztikus és nemdeterminisztikus változat, egyenértékűségük, példák, néhány gyakorlati alkalmazás (véges nyelv, KMP)

11. A szóprobléma lineáris idejű megoldása 3. típus esetén véges determinisztikus automatákkal (L_{VDA =} L₃).

12. A kis Bar-Hillel lemma (bizonyítással) és alkalmazása, L₃Ì L_2.

13. Reguláris nyelvek, illetve kifejezések, Kleene tétele (bizonyítással).

14. Maradéknyelvek, Myhill Nerode tétele, minimális automata konstrukciója maradéknyelvekkel.

15. A szóprobléma köbös idejű megoldása 2. típus esetében (CYK algoritmus).

16. A 2 típusú nyelvtanok által generált nyelvek jellemzése szintaxis-fákkal, a nagy Bar-Hillel lemma (bizonyítással) és alkalmazása, L₂Ì L₁.

17. Verem-automaták, példák. L_V= L₂. Determinisztikus változat és hatóereje.

A dőlten szedett részek a jegyzetben másképp vannak benne, illetve csak az előadáson voltak.

A vizsgán négy bizonyítást kérek részletesen (kövéren kiemelve vannak), a többi esetekben csak a konstrukciót várom.