|
|
|
||
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ů.
Poslední úprava: Kubová Petra (02.01.2018)
|
|
||
Pro zı́skánı́ zápočtu je potřeba dostatek bodů ze zápočtových testů. Zkouška se skládá z povinné pı́semné a povinné ústnı́ části. Poslední úprava: Svozil Daniel (07.02.2018)
|
|
||
Z:Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. "Compilers: Principles, Techniques, and Tools" (2nd Edition). Addison Wesley, 2007. ISBN 0321486811. Z:Kozen, D. C. "Automata and Computability". Springer, 1997. ISBN 0387949070. Z:Melichar, B., Holub, J., Mužátko, P. "Languages and Translations". Praha: Publishing House of CTU, 1997. ISBN 80-01-01692-7. Poslední úprava: Kubová Petra (02.01.2018)
|
|
||
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. Poslední úprava: Kubová Petra (02.01.2018)
|
|
||
https://edux.fit.cvut.cz/courses/BI-AAG/ (nutné přihlášení) Poslední úprava: Kubová Petra (02.01.2018)
|
|
||
Studenti budou umět: budou mít 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ů. budou znát hierarchii formálních jazyků a rozumějí vztahům mezi formálními jazyky a automaty. aplikovat znalosti z teorie automatů 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ů. Poslední úprava: Kubová Petra (02.01.2018)
|
|
||
Znalosti základních datových struktur a základů programování. Poslední úprava: Kubová Petra (02.01.2018)
|
Zátěž studenta | ||||
Činnost | Kredity | Hodiny | ||
Účast na přednáškách | 1 | 28 | ||
Příprava na přednášky, semináře, laboratoře, exkurzi nebo praxi | 1 | 28 | ||
Práce na individuálním projektu | 2 | 56 | ||
Příprava na zkoušku a její absolvování | 1 | 28 | ||
Účast na seminářích | 1 | 28 | ||
6 / 6 | 168 / 168 |
Hodnocení studenta | |
Forma | Váha |
Zkouškový test | 30 |
Průběžné a zápočtové testy | 40 |
Ústní zkouška | 30 |