Automaty a gramatiky
TIN071, 2/2 Zk, Z, letní semestr

Roman Barták, KTIML

---

Zdroje  |  Přednáška  |  Cvičení  |  Zkouška  |  Kontakt

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontexové a kontextové gramatiky).

Zdroje:	nahoru

M. Chytil: Automaty a gramatiky, SNTL Praha, 1984
V. Koubek: Automaty a gramatiky, elektronický text, 1996 [PostScript]
R. Barták: Automaty a gramatiky: on-line, 2001(tyto stránky)
P. Jančar: Teorie jazyků a automatů, přednáška na VŠB Ostrava, [WWW]
I. Černá, M. Křetínský, A. Kučera: Formální automaty a jazyky I, Masarykova Univerzita [WWW]

M. Chytil: Teorie automatů a formálních jazyků, skripta
M. Chytil: Sbírka řešených příkladů z teorie automatů a formálních jazyků, skripta
M. Demlová, V. Koubek: Algebraická teorie automatů, SNTL Praha, 1990

J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

Přednáška (LS 2011/2012): úterý 09:00 - 10:30, posluchárna S3 (Malá Strana, 3. patro)	nahoru

Tento rozvrh je předběžný a je možné, že bude v průběhu semestru modifikován.

21. 02. 2012	Úvod, historie, definice a příklady konečných automatů. Nerodova věta a její použití.
28. 02. 2012	Iterační (pumping) lemma. Ekvivalence automatů a dosažitelnost stavů. Ekvivalence stavů, automatová kongruence, podílový automat. Redukce automatu.
06. 03.2012	Věta o izomorfismu.Normalizace konečných automatů.Nedeterministické konečné automaty. Definice dvoucestného automatu.
13. 03. 2012	Dvoucestné automaty a jejich ekvivalence s konečnými automaty. Uzávěrové vlastnosti (množinové a řetězcové operace, substituce, kvocienty).
20. 03. 2012	Kleeneova věta. Regulární výrazy. Převod regulární výrazu na automat a zpět. Mooreův a Mealyho stroj.
27. 03. 2012	Úvod do gramatik. Přepisovací systémy. Chomského hierarchie. Regulární gramatiky, ekvivalence s konečnými automaty, lineární gramatiky.
03. 04. 2012	Bezkontextové gramatiky a jejich redukce. Kanonické derivace, derivační stromy, jednoznačné/víceznačné gramatiky.
10. 04. 2012	Zásobníkové automaty: vztah přijímání prázdným zásobníkem a koncovým stavem. Od gramatiky k automatu.
17. 04. 2012	Od automatu ke gramatice. Deterministické zásobníkové automaty. Greibachové normální tvary bezkontextových gramatik.
24 .04. 2012	Chomského normální tvar bezkontextových gramatik. Iterační (pumping) lemma. Dyckovy jazyky. Uzávěrové vlastnosti (množinové a řetězcové operace, substituce, kvocienty).
01. 05. 2012	svátek práce
08. 05. 2012	den vítězství
15. 05. 2012	Dokončení uzávěrových vlastností BKJ. Kontextové gramatiky, věta o monotonii. Úvod do Turingových strojů. Převod stroje na gramatiku a zpět.
22. 05. 2012	Lineárně omezené automaty. Algoritmicky nerozhodnutelné problémy, Postův korespondenční problém. Závěrečné shrnutí.

Kompletní přednáška je ka stažení také ve formátu PDF pro e-čtečky a iPad.

Cvičení:	nahoru

Vyzkoušejte si své znalosti na příkladech.

Konstrukce konečných automatů.
Nerodova věta, iterační lemma a jejich použití. Ekvivalence stavů.
Rozšířené iterační lemma. Redukce automatů a hledání rozlišujících slov
Operace s regulárními jazyky.
Regulární výrazy a konečné automaty.
Dvousměrné automaty. Mealyho a Mooreovy stroje.
Úvod do gramatik, pravě lineární gramatiky a konečné automaty.
Bezkontextové gramatiky, redukce a derivační stromy.
Zásobníkové automaty.
Normální tvary BKG a lemma o vkládání.

Zkouška:	nahoru

Základem zkoušky je písemná práce skládající se ze dvou částí: kvizu a příkladu. Kviz je formou výběru správných odpovědí (může jich být více nebo také žádná) na položené otázky a je z něj potřeba získat minimální počet bodů pro postup do další části zkoušky (příkladu) - ukázka kvizových otázek. Příklad typicky obsahuje konstrukci automatu/gramatiky, formulaci vět a důkazy. Zkoušena je látka probraná na přednášce a cvičeních. Pro úspěšné složení zkoušky je nutno chápat principy a také je umět přesně formálně zapsat. Před zkoušet je potřeba mít udělen zápočet! Na zkoušku se zapisuje prostřednictvím Studijního informačního systému.

Kontakt:	nahoru

Doc. RNDr. Roman Barták, Ph.D. Katedra teoretické informatiky a matematické logiky Matematicko-fyzikální fakulta Univerzity Karlovy Malostranské nám. 2/25, 118 00 Praha 1 Czech Republic e-mail: bartak (AT) ktiml.mff.cuni.cz tel: +420 221 914 242

V případě potřeby je možné domluvit individuální konzultace k přednášce. Samozřejmě veškeré komentáře k přednášce, hlášení chyb, nejasných pasáží apod. jsou vítány.