Automaty a gramatiky
| 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/ This course is presented in Czech.
However, there is an English variant in the program Informatics (B1801 / 4753).
- 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 St Čt Pá - Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Bc. specializace Informační bezpečnost, 2021 (povinný předmět programu)
- Bc. specializace Manažerská informatika, 2021 (povinný předmět programu)
- Bc. specializace Počítačová grafika, 2021 (povinný předmět programu)
- Bc. specializace Počítačové inženýrství, 2021 (povinný předmět programu)
- Bc. program, pro fázi studia bez specializace, 2021 (povinný předmět programu)
- Bc. specializace Webové inženýrství, 2021 (povinný předmět programu)
- Bc. specializace Umělá inteligence, 2021 (povinný předmět programu)
- Bc. specializace Teoretická informatika, 2021 (povinný předmět programu)
- Bc. specializace Softwarové inženýrství, 2021 (povinný předmět programu)
- Bc. specializace Počítačové systémy a virtualizace, 2021 (povinný předmět programu)
- Bc. specializace Počítačové sítě a Internet, 2021 (povinný předmět programu)
- Bc. specializace Informační bezpečnost, 2024 (povinný předmět programu)
- Bc. program, pro fázi studia bez specializace, 2024 (povinný předmět programu)
- Bc. specializace Manažerská informatika, 2024 (povinný předmět programu)
- Bc. specializace Počítačová grafika, 2024 (povinný předmět programu)
- Bc. specializace Softwarové inženýrství, 2024 (povinný předmět programu)
- Bc. specializace Webové inženýrství, 2024 (povinný předmět programu)
- Bc. specializace Počítačové sítě a Internet, 2024 (povinný předmět programu)
- Bc. specializace Počítačové inženýrství, 2024 (povinný předmět programu)
- Bc. specializace Počítačové systémy a virtualizace, 2024 (povinný předmět programu)
- Bc. specializace Umělá inteligence, 2024 (povinný předmět programu)
- Bc. specializace Teoretická informatika, 2024 (povinný předmět programu)
- Bc. specializace Počítačová grafika s vynecháním BI-SVZ (povinný předmět programu)