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

poslední změna: 16-10-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. Mooreův algoritmus minimalizace.
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. Bezkontextové gramatiky.
4.11. [cvičení 3] 1) Determinizace konečného automatu.
2) Minimalizace konečného automatu.