Automaty a gramatiky

Letní semestr 2008/2009
úterý 14:00 - 15:30 (S3)

24.02. 2009	Úvod, historie, definice a příklady konečných automatů. Nerodova věta a její použití, iterační (pumping) lemma.
03.03. 2009	Ekvivalence automatů a dosažitelnost stavů. Ekvivalence stavů, automatová kongruence, podílový automat. Redukce automatu. Věta o izomorfismu. Normalizace konečných automatů.
10.03.2009	Nedeterministické konečné automaty. Dvoucestné automaty a jejich ekvivalence s konečnými automaty.
17.03. 2009	Uzávěrové vlastnosti (množinové a řetězcové operace, substituce, kvocienty). Kleeneova věta.
24.03. 2009	Regulární výrazy. Převod regulární výrazu na automat a zpět. Mooreův a Mealyho stroj.
31.03. 2009	odpadá
07.04. 2009	Úvod do gramatik. Přepisovací systémy. Chomského hierarchie. Regulární gramatiky, ekvivalence s konečnými automaty, lineární gramatiky.
14.04. 2009	Bezkontextové gramatiky a jejich redukce. Kanonické derivace, derivační stromy, jednoznačné/víceznačné gramatiky.
21.04. 2009	Zásobníkové automaty. Přijímání prázdným zásobníkem a koncovým stavem. Od gramatiky k automatu a zpět.
28.04. 2009	Deterministické zásobníkové automaty. Normální tvary bezkontextových gramatik (Greibachové, Chomského). Iterační (pumping) lemma.
05.05. 2009	Dyckovy jazyky. Uzávěrové vlastnosti (množinové a řetězcové operace, substituce, kvocienty). Kontextové gramatiky, věta o monotonii.
12.05. 2009	Úvod do Turingových strojů. Převod stroje na gramatiku a zpět. Lineárně omezené automaty. Algoritmicky nerozhodnutelné problémy.
19.05. 2009	pravděpodobně odpadne

Publikovaný rozvrh je předběžný a je možné a také pravěpodobné, že se bude během semestru měnit.

Přednáška	Automaty a gramatiky
Úvod \| Sylabus \| Zdroje \| Přednáška \| Cvičení \| Zkoušky