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

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.21 Z,ZK 5 2P+2C česky
Garant předmětu:
Jan Holub
Přednášející:
Jan Holub, Jan Janoušek
Cvičící:
Dominika Bohuslavová, Suzan Catay, Jiří Lejsek, Tomáš Pecka, Štěpán Plachý, Jiří Skotal, Martin Svoboda, Ondřej Štorc, Tomáš Vesecký, Patrik Vodila
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 použití bezkontextových gramatik a konstrukci a použití zásobníkových automatů a o překladových gramatikách automatech. Znají hierarchii formálních jazyků a rozumějí vztahům mezi formálními jazyky a automaty. Jsou seznámeni s Turingovým strojem a s třídami složitosti P a NP.

Požadavky:

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

Osnova přednášek:

1. Základní pojmy, Chomského hierarchie.

2. Deterministické a nedeterministické konečné automaty.

3. Operace s automaty.

4. Regulární výrazy.

5. Převody mezi regulárními gramatikami, regulárními výrazy a konečnými automaty.

6. Vlastnosti regulárních jazyků.

7. Bezkontextové gramatiky.

8. Zásobníkové automaty. Syntaktická analýza.

9. Překladové gramatiky a automaty.

10. Jazyky kontextové, rekurzivně spočetné a rekurzivní. Turingův stroj.

11. Časová složitost, třídy P a NP.

12. Programová a obvodová realizace konečných automatů.

13. Konečný automat jako lexikální analyzátor.

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. Sipser M. : Introduction to the Theory of Computation. Cengage Learning Custom Publishing, 2020. ISBN 978-0357670583.

2. Hopcroft J.E., Motwani R., Ullman J. D. : Introduction to Automata Theory, Languages, and Computation, 3rd Edition. Pearson, 2008. ISBN 978-8131720479.

3. Kozen D. C. : Automata and Computability. Springer, 1997. ISBN 978-0387949079.

4. Šestáková E.: Automaty a gramatiky: Sbírka řešených příkladů, ČVUT 2017, ISBN 978-80-01-06306-4

5. Šestáková E.: Automata and Grammars, A Collection of exercises and Solutions, ČVUT, 2018, ISBN 978-80-01-06462-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 2024/2025:
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
Ú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-1442
Plachý Š.
16:15–17:45
(paralelka 1)
Thákurova 7 (budova FSv)
místnost TH:A-1442
Plachý Š.
18:00–19:30
(paralelka 2)
Thákurova 7 (budova FSv)
místnost TK:BS
Janoušek J.
14:30–16:00
(přednášková par. 2)
Dejvice
NTK Ballingův sál
St
místnost T9:301
Bohuslavová D.
07:30–09:00
(paralelka 3)
Dejvice
NBFIT učebna
místnost T9:301
Štorc O.
09:15–10:45
(paralelka 4)
Dejvice
NBFIT učebna
místnost TH:A-942
Plachý Š.
14:30–16:00
(paralelka 6)
Thákurova 7 (budova FSv)
místnost TH:A-942
Vesecký T.
Lejsek J.

16:15–17:45
(paralelka 7)
Thákurova 7 (budova FSv)
místnost TH:A-942
Lejsek J.
Vesecký T.

18:00–19:30
(paralelka 8)
Thákurova 7 (budova FSv)
místnost TH:A-942
Skotal J.
07:30–09:00
(paralelka 18)
Thákurova 7 (budova FSv)
místnost TH:A-1442
Catay S.
09:15–10:45
(paralelka 5)
Thákurova 7 (budova FSv)
Čt
místnost TH:A-942
Bohuslavová D.
07:30–09:00
(paralelka 9)
Thákurova 7 (budova FSv)
místnost TH:A-942
Pecka T.
09:15–10:45
(paralelka 10)
Thákurova 7 (budova FSv)
místnost TH:A-942
Pecka T.
11:00–12:30
(paralelka 11)
Thákurova 7 (budova FSv)
místnost T9:301
Svoboda M.
12:45–14:15
(paralelka 12)
Dejvice
NBFIT učebna
místnost T9:301
Svoboda M.
14:30–16:00
(paralelka 13)
Dejvice
NBFIT učebna
místnost T9:301
Svoboda M.
16:15–17:45
(paralelka 14)
Dejvice
NBFIT učebna
místnost T9:301
Svoboda M.
18:00–19:30
(paralelka 15)
Dejvice
NBFIT učebna
místnost TH:A-942
Štorc O.
18:00–19:30
(paralelka 22)
Thákurova 7 (budova FSv)

místnost TH:A-1247
Plachý Š.
11:00–12:30
(paralelka 16)
Thákurova 7 (budova FSv)
seminární místnost
místnost T9:301
Pecka T.
12:45–14:15
(paralelka 17)
Dejvice
NBFIT učebna
místnost TH:A-1247
Vodila P.
16:15–17:45
(paralelka 20)
Thákurova 7 (budova FSv)
seminární místnost
místnost TH:A-1242
Plachý Š.
16:15–17:45
(paralelka 21)
Thákurova 7 (budova FSv)
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 10. 10. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6546306.html