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

poslední změna: 11-11-2025

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.

zápočet

Podmínkou udělení zápočtu je vypracování a předvedení 6 zápočtových úloh na (alespoň) 4 různých cvičeních během semestru. Zápočtové úlohy budou vzeřejněné vždy minimálně týden předem v podrobném sylabu níže.

Podrobný sylabus 2024/2025

datum náplň předášky/cvičení
23.9. Základní pojmy z teorie formálních jazyků. Konečný automat, výpočet, jazyk rozeznávaný konečným automatem.
26.9. Mmožina Rec Σ*. Uzavřenost Rec Σ* na zrcadlový obraz, sjednocení, průnik a levý kvocient.
30.9. Užitečný automat. Prázdnost a nekonečnost jazyka rozeznávaného KA. Věty o vkládání.
3.10. Automaty s ε-přechody. Regulární výrazy a jazyky popsané regulárními výrazy.
7.10. Kleenova věta. Uzavřenost Rec Σ* na zřetězení a iteraci. Algoritmus Brzozowski-McClusky, Ardenovo lemma.
10.10. Deterministické konečné automaty. Rozhodování ekvivalence konečných automatů. Uzavřenost Rec Σ* na obraz a vzor při morfizmu.
14.10. [cvičení 1] 1) Konstrukce konečných automatů.
2) Rozhodování neregularity jazyka pomocí vět o vkládání.
» Zadání zápočtových úloh a dalších příkladů k procvičení «
17.10. Minimální automat jazyka.
21.10. [cvičení 2] 1) Hierarchie vět o vkládání.
2) Kleenova věta: převod KA ↔ reg. výraz.
» Zadání zápočtových úloh a dalších příkladů k procvičení «
24.10. —
28.10. —
31.10. Myhilova-Nerodeova věta. Mooreův algoritmus minimalizace. Generativní gramatiky.
4.10. Bezkontextové gramatiky. Jazyk generovaný BKG. Derivační stromy. Jednoznačnost BKG.
7.10. BKG bez zbytečných symbolů, bez ε-pravidel a jednotkových pravidel. Chomského normální forma.
11.11. [cvičení 3] 1) Determinizace konečného automatu.
2) Minimalizace konečného automatu.
» Zadání zápočtových úloh a dalších příkladů k procvičení «
14.11. Vlastnosti BKJ.
18.11.
21.11.
25.11. [cvičení 4]
28.11.
2.12. [cvičení 5]