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:

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 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).

lecture
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.
lecture
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.
lecture
05. 04. 2013 Bezkontextové gramatiky a jejich redukce. Kanonické derivace, derivační stromy, jednoznačné/víceznačné gramatiky.
lecture
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.
lecture
19. 04. 2013 Od automatu ke gramatice. Deterministické zásobníkové automaty. Greibachové normální tvary bezkontextových gramatik.
lecture
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).
lecture
03. 05. 2013 Dokončení uzávěrových vlastností BKJ. lecture
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í.
lecture
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 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.