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

last change: 21-10-2024

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 2024/2025

datum náplň předášky/cvičení
23.9. Základní pojmy z teorie jazyků. Konečný automat, výpočet, jazyk rozeznávaný konečným automatem. Mmožina Rec A*.
24.9. Uzavřenost Rec A* na zrcadlový obraz, sjednocení, průnik a levý kvocient. Užitečný automat.
30.9. Prázdnost a nekonečnost jazyka rozeznávaného KA. Věty o vkládání. Automaty s ε-přechody.
1.10. Regulární jazyky a regulární výrazy. Kleenova věta (Reg A* ⊆ Rec A*): standardní automaty, uzavřenost Rec A* na zřetězení a iteraci.
7.10. [cv1] Konstrukce konečných automatů. Rozhodování neregularity jazyka pomocí vět o vkládání. Hierarchie vět o vkládání.
8.10. Kleenova věta (Rec A* ⊆ Reg A*): algoritmus Brzozowski-McClusky, Ardenovo lemma.
14.10. Deterministické konečné automaty. Rozhodování ekvivalence konečných automatů. Uzavřenost Rec A* na obraz a vzor při morfizmu.
15.10. Minimální automat jazyka. Mooreův algoritmus minimalizace.
21.10. Myhillova-Nerodeova věta.
22.10. [cv2] Standardní automaty, Kleenova věta.
28.10. —
29.10. —