Automaty
a gramatiky
TIN071,
2/2 Zk, Z, letní semestr
Roman Barták, KTIML
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: 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, 1990J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
Přednáška (LS 2012/2013):
pátek 09:00 - 10:30, posluchárna S3 (Malá Strana, 3. patro)Tento rozvrh je přeběžný a s velkou pravděpodobností bude v průběhu semestru mírně modifikován (zvláště v jeho závěru ;-).
22. 02. 2013 Úvod, historie, definice a příklady konečných automatů. Nerodova věta a její použití.
01. 03. 2013 Iterační (pumping) lemma. Ekvivalence automatů a dosažitelnost stavů. Ekvivalence stavů, automatová kongruence, podílový automat. Redukce automatu.
08. 03. 2013 Věta o izomorfismu.Normalizace konečných automatů.Nedeterministické konečné automaty. Definice dvoucestného automatu.
15. 03. 2013 Dvoucestné automaty a jejich ekvivalence s konečnými automaty. Uzávěrové vlastnosti (množinové a řetězcové operace, substituce, kvocienty).
22. 03. 2013 Kleeneova věta. Regulární výrazy. Převod regulární výrazu na automat a zpět. Mooreův a Mealyho stroj. 29. 03. 2013 Úvod do gramatik. Přepisovací systémy. Chomského hierarchie. Regulární gramatiky, ekvivalence s konečnými automaty, lineární gramatiky. 05. 04. 2013 Bezkontextové gramatiky a jejich redukce. Kanonické derivace, derivační stromy, jednoznačné/víceznačné gramatiky. 12. 04. 2013 Zásobníkové automaty: vztah přijímání prázdným zásobníkem a koncovým stavem. Od gramatiky k automatu. 19. 04. 2013 Od automatu ke gramatice. Deterministické zásobníkové automaty. Greibachové normální tvary bezkontextových gramatik. 26 .04. 2013 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). 03. 05. 2013 Dokončení uzávěrových vlastností BKJ. 10. 05. 2013 Kontextové gramatiky, věta o monotonii. Úvod do Turingových strojů. Převod stroje na gramatiku a zpět.
17. 05. 2013 Lineárně omezené automaty. Algoritmicky nerozhodnutelné problémy, Postův korespondenční problém. Závěrečné shrnutí. 24. 05. 2013 odpadá
Kompletní přednáška je ka stažení také ve formátu PDF pro e-čtečky a iPad.
Cvičení: 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í. |
|
Exercises in English can be downloaded in PDF.
Zkouška: 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:
prof. 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 Republice-mail: bartak (AT) ktiml.mff.cuni.cz
tel: +420 221 914 242V 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.