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

poslední změna: 09-12-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. Věta o vkládání pro BKJ. Uzavřenost třídy BKJ na sjednocení, zřetězení a iteraci.
18.11. Práznost a nekonečnost jazyka generovaného BKG. Zásobníkové automaty. Konfigurace a výpočet ZA.
21.11. Jazyk přijímaný ZA. Ekvivalence přijímání koncovým stavem a prázdným zásobníkem. Průnik jazyka přijímaného ZA s regulárním jazykem.
25.11. [cvičení 4]
1) Konstrukce BKG.
2) Speciální formy BKG.
» Zadání zápočtových úloh «
28.11. Ekvivalence BKG a ZA. (Ne)rozhodnutelnost. Algoritmicky a turingovsky vyčíslitelné funkce. Churchova-Turingova téze.
2.12. [cvičení 5]
1) Konstrukce zásobníkových automatů.
2) Pumping lemma pro BKJ, uzávěrové vlasnosti třídy ℒBKJ.
» Zadání zápočtových úloh a dalších příkladů k procvičení «
5.12. Algoritmicky vyčíslitelné funkce. Turingův stroj. Rekurzivní a rekurzivně spočetný jazyk.
9.12. Modifikace TS (více řádek, více pásek, nedeterminismus, omezení páskové abecedy).