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