Jazyky, automaty a vyčíslitelnost (01JAV)

poslední změna: 05-05-2020

Anotace

Konečné automaty a regulární jazyky, bezkontextové jazyky a zásobníkové automaty, kontextové jazyky a lineárně omezené automaty, jazyky typu 0 a Turingovy stroje. Algoritmy a algoritmicky vyčíslitelné funkce. Rekurzívní funkce, rekurzívní a rekurzívně spočetné množiny. Algoritmicky neřešitelné problémy.

Podrobný sylabus

-->
datum náplň předášky/cvičení
17.2. Základní pojmy z teorie jazyků. Konečný automat, výpočet, jazyk rozeznávaný konečným automatem. Mmožina Rec A*.
21.2. Uzavřenost Rec A* na zrcadlový obraz, sjednocení, průnik a levý kvocient. Užitečný automat. Prázdnost a nekonečnost jazyka rozeznávaného KA.
24.2.
25.2. Věty o vkládání. Automaty s ε-přechody. Regulární jazyky a regulární výrazy.
2.3. [cv1] Konstrukce konečných automatů. Rozhodování neregularity jazyka pomocí vět o vkládání. Hierarchie vět o vkládání.
3.3. Kleenova věta. Reg A* ⊆ Rec A*: standarní automaty, uzavřenost Rec A* na zřetězení a iteraci. Rec A* ⊆ Reg A*: MNY algoritmus.
9.3. Rec A* ⊆ Reg A*: BMC algoritmus, Ardenovo lemma. Deterministický automat, algoritmus determinizace.
10.3.
16.3. Ekvivalence KA. Myhill-Nerodeova věta. Minimální automat jazyka. Algoritmus minimalizace.
17.3. [cv2] Standardní automaty. Přechod automat -> jazyk: algoritmy MNY a BMC.
23.3. Postačující podmínka pro regularitu jazyka (Ehrenfeucht–Parikh–Rozenberg).
[cv3] Algoritmy determinizace a minimalizace KA.
24.3. Bezkontextové gramatiky. Jazyk generovaný BKG. Derivační stromy. Jednoznačnost BKG.
30.3. Redukce BKG: zbytečné symboly, ε-pravidla, jednotková pravidla. Chomského a Greibachové normální forma.
31.3. Zásobníkový automat, konfigurace a výpočet zásobníkového automatu. Ekvivalence rozeznávání prázným zásobníkem a koncovým stavem.
6.4. Ekvivalence BKG a zásobníkových automatů.
7.4. [cv4] Konstrukce BKG. Jednoznačnost BKG.
14.4. [cv5] Kontrukce zásobníkových automatů. Převod BKG na ZA. Věta o vkládání pro BKJ.
20.4. Pumping lemma pro bezkontextové jazyky. Uzavřenosti třídy BKJ. Prázdnost, konečnost a nekonečnost BKJ.
21.4. Algoritmicky vyčíslitelné funkce. Turingův stroj. Rekurzivní a rekurzivně spočetný jazyk. Turingovsky vyčíslitelné funkce. Turingova téze.
27.4. Vícepáskový a nedeterministický TS. TS a ZA.
28.4. Nerozhodnutelnost. Uzávěrové vlastnosti tříd LRS a LREK. Diagonální jazyk Ld.
4.5. Univerzální jazyk Lu. Jazyky LNE a LE. Riceova věta. RS vlastností RS jazyků.
Riceova věta. Postův korespondenční problém. Nerozhodnutelné vlastnosti BKJ.
Chomského hierarchie.