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

poslední změna: 15-05-2017

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í
20.2. Historie teorie automatů. Základní pojmy z teorie jazyků. Konečný automat, výpočet, jazyk rozeznávaný konečným automatem.
22.2. Mmožina Rec A*. Uzavřenost na transpozici, sjednocení, průnik a (levý) kvocient.
23.2. Užitečný stav, trim automat. Prázdnost a nekonečnost jazyka rozeznávaného KA. Věty o vkládání.
1.3. [cv1] Konstrukce konečných automatů. Zamíchání slov. Rozhodování neregularity jazyka pomocí levého kvocientu.
8.3. Automaty s ε-přechody. Regulární jazyky. Kleenova věta.
9.3. Reg A* ⊆ Rec A*: normální a standarní automaty. Uzavřenost Rec A* na zřetězení a iteraci.
15.3. Rec A* ⊆ Reg A*: MNY algoritmus, BMC algoritmus.
16.3. [cv2] Rozhodování neregularity jazyka pomocí vět o vkládání. Normalizované automaty, realizace regulárních operací.
20.3. Deterministický automat, algoritmus determinizace. Automat levých kvocientů, minimální automat jazyka.
22.3. Algoritmy minimalizace (Moore, Brzozowski). Postačující podmínka pro regularitu jazyka (Ehrenfeucht–Parikh–Rozenberg).
29.3.
30.3. [cv3] Standardní automaty, realizace regulárních operací. Přechod automat->jazyk: algoritmus McNaughton-Yamada, algoritmus Brzozowski-McCluskey, Ardenovo lemma.
3.4. Bezkontextové gramatiky. Jazyk generovaný BKG. Derivační stromy.
5.4. Redukce BKG: zbytečné symboly, ε-pravidla.
12.4. Redukce BKG: jednotková pravidla. Chomského a Greibachové normální forma. Zásobníkový automat, výpočet zásobníkového automatu, jazyk rozeznávaný zásobníkovým automatem. Deterministické ZA.
13.4. [cv4] Determinizace a minimalizace konečných automatů.
19.4. Ekvivalence rozeznávání prázným zásobníkem a koncovým stavem. BKJ jsou právě jazyky rozeznávané zásobníkovými automaty.
20.4. Pumping lemma pro bezkontextové jazyky. Uzavřenost BKJ na sjednocení, zřetězení a iteraci.
24.4. Průnik a doplněk BKJ. Průnik bezkontextového jazyka s jazykem regulárním. Prázdnost, konečnost a nekonečnost BKJ. Algoritmus CYK (membership problem).
26.4. [cv5] Konstrukce bezkontextových gramatik zásobníkových automatů. Jednoznačnost BKG.
2.5. Turingův stroj. Rekurzivní a rekurzivně spočetný jazyk. Parciálně rekurzivní a rekurzivní funkce.
3.5. Metody návrhu turingových strojů (paměť v řídící jednotce, víceřádková páska). Vícepáskový a nedeterministický TS. TS jako generátor.
4.5. [cv6] Redukce BKG, Chomského normální forma. Převod BKG na ZA.
10.5. Nerozhodnutelnost. Uzavřenosti tříd RS a REK. Diagonální jazyk Ld a univerzální jazyk Lu.
15.5. Riceova věta. Postův korespondenční problém. Nerozhodnutelné vlastnosti BKJ.