Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2020/2021

Automaty a gramatiky

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
BI-AAG Z,ZK 6 2P+2C česky
Přednášející:
Jan Janoušek, Jan Holub (gar.)
Cvičící:
Tomáš Pecka, Štěpán Plachý, Jan Pokorný, Radomír Polách, Martin Svoboda, Eliška Šestáková, Jan Trávníček
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Studenti získají základní teoretické a implementační znalosti o konstrukci, použití a vzájemných transformací konečných automatů, regulárních výrazů a regulárních gramatik, o překladových konečných automatech a o konstrukci a použití zásobníkových automatů. Znají hierarchii formálních jazyků a rozumějí vztahům mezi formálními jazyky a automaty. Znalosti z teorie automatů umějí aplikovat pro řešení praktických problémů z oblasti vyhledávání v textu, kompresi dat, jednoduchých překladů a návrhu číslicových obvodů.

Požadavky:

Znalosti základních datových struktur a základů programování.

Osnova přednášek:

1. Motivace pro studium formálních jazyků. Základní pojmy (jazyk, abeceda, gramatika, automat), Chomského hierarchie.

2. Deterministické a nedeterministické konečné automaty (DKA a NKA), NKA s epsilon přechody.

3. Operace s automaty (převod na NKA bez epsilon přechodů, na DKA, minimalizace), průnik, sjednocení.

4. Programová realizace DKA a NKA, obvodová realizace.

5. Rozšíření o překlad, Mealey, Moore, převody.

6. Operace s regulárními gramatikami, převody na KA.

7. Regulární výrazy, převody mezi regulárními výrazy, konečnými automaty a regulárními gramatikami, Kleenova věta.

8. Principy využití regulárních výrazů v UNIXu (grep, egrep, perl, PHP, ...).

9. Konečný automat jako lexikální analyzátor, lex/flex generátory.

10. Vlastnosti regulárních jazyků (pumping lemma, Nerodova věta).

11. Jazyky bezkontextové, zasobníkový automat.

12. Analýza bezkontextových jazyků (nedeterministická versus deterministická).

13. Jazyky kontextové a neomezené, Turingův stroj. Třídy P, NP, NPC, NPH.

Osnova cvičení:

1. Ukázky formálních jazyků. Intuitivní návrh gramatik pro jazyky zadané množinově. Odhad umístění jazyka v Chomského hierarchii.

2. Intuitivní návrh konečných automatů (DKA, NKA, s epsilon-přechody) pro zadaný jazyk.

3. Převody a kompozice KA.

4. Implementace KA.

5. Návrh KA s výstupní funkcí a jeho implementace.

6. Převody gramatik na KA a zpět.

7. Návrh, úpravy a převody regulárních výrazů.

8. Využití regulárních výrazů pro řešení úloh ze zpracování textu (např. sh, grep, sed, perl).

9. Návrh a implementace lexikálního analyzátoru.

10. Klasifikace jazyků.

11. Příklady bezkontextových jazyků, návrh zásobníkových automatů.

12. Ukázky deterministické analýzy bezkontextových jazyků (např. LL, yacc, bison).

13. Příklady kontextových a neomezených jazyků, návrh gramatik a Turingových strojů.

Cíle studia:

Předmět si klade za cíl seznámit studenty s konečnými automaty, regulárními výrazy, gramatikami a překladovými konečnými automaty s důrazem na praktické využití. Dále pak seznámí studenta s třídou bezkontextových jazyků, základním použitím zásobníkových automatů a s hierarchií jazyků pro jeho snazší orientaci v problematice. Znalosti získané v tomto předmětu naleznou uplatnění při návrhu algoritmů pro vyhledávání vzorků, kompresi dat, překlad, jednoduchou syntaktickou analýzu a při návrhu číslicových obvodů.

Studijní materiály:

1. Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. „Compilers: Principles, Techniques, and Tools“ (2nd Edition). Addison Wesley, 2007. ISBN 0321486811.

2. Kozen, D. C. „Automata and Computability“. Springer, 1997. ISBN 0387949070.

3. Melichar, B., Holub, J., Mužátko, P. „Languages and Translations“. Praha: Publishing House of CTU, 1997. ISBN 80-01-01692-7.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-AAG/

Další informace:
https://courses.fit.cvut.cz/BI-AAG/
Rozvrh na zimní semestr 2020/2021:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost T9:343
Pecka T.
11:00–12:30
(paralelka 4)
Dejvice
NBFIT učebna
místnost T9:347
Pecka T.
16:15–17:45
(paralelka 10)
Dejvice
NBFIT učebna
místnost T9:347
Pecka T.
18:00–19:30
(paralelka 18)
Dejvice
NBFIT učebna
místnost T9:350
Polách R.
16:15–17:45
(paralelka 21)
Dejvice
NBFIT PC ucebna
Út
místnost TK:BS
Holub J.
12:45–14:15
(přednášková par. 1)
Dejvice
NTK Ballingův sál
místnost TH:A-942
Plachý Š.
16:15–17:45
(paralelka 1)
Thákurova 7 (FSv-budova A)
místnost TH:A-942
Plachý Š.
18:00–19:30
(paralelka 2)
Thákurova 7 (FSv-budova A)
místnost TK:BS
Janoušek J.
16:15–17:45
(přednášková par. 2)
Dejvice
NTK Ballingův sál
místnost T9:343
Pecka T.
18:00–19:30
(paralelka 3)
Dejvice
NBFIT učebna
St
místnost TH:A-1242
Polách R.
09:15–10:45
(paralelka 5)
Thákurova 7 (FSv-budova A)
místnost T9:343
Polách R.
12:45–14:15
(paralelka 6)
Dejvice
NBFIT učebna
místnost T9:343
Šestáková E.
16:15–17:45
(paralelka 8)
Dejvice
NBFIT učebna
místnost T9:343
Šestáková E.
18:00–19:30
(paralelka 9)
Dejvice
NBFIT učebna
místnost T9:343
Šestáková E.
14:30–16:00
(paralelka 7)
Dejvice
NBFIT učebna
Čt
místnost TH:A-942
Svoboda M.
12:45–14:15
(paralelka 11)
Thákurova 7 (FSv-budova A)
místnost TH:A-942
Svoboda M.
14:30–16:00
(paralelka 12)
Thákurova 7 (FSv-budova A)
místnost TH:A-942
Svoboda M.
16:15–17:45
(paralelka 14)
Thákurova 7 (FSv-budova A)
místnost TH:A-942
Svoboda M.
18:00–19:30
(paralelka 16)
Thákurova 7 (FSv-budova A)
místnost TH:A-1247
Trávníček J.
14:30–16:00
(paralelka 13)
Thákurova 7 (FSv-budova A)
seminární místnost
místnost T9:302
Šestáková E.
16:15–17:45
(paralelka 15)
Dejvice
NBFIT učebna
místnost T9:302
Šestáková E.
18:00–19:30
(paralelka 17)
Dejvice
NBFIT učebna

místnost T9:346
Plachý Š.
11:00–12:30
(paralelka 19)
Dejvice
NBFIT učebna
místnost T9:346
Plachý Š.
12:45–14:15
(paralelka 20)
Dejvice
NBFIT učebna
místnost T9:302
Pokorný J.
16:15–17:45
(paralelka 22)
Dejvice
NBFIT učebna
Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 22. 10. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1122206.html