Automaty a gramatiky - B500005
Anglický název: Automata and Grammars
Zajišťuje: Ústav informatiky a chemie (143)
Fakulta: Fakulta chemické technologie
Platnost: od 2021 do 2022
Semestr: zimní
Body: zimní s.:6
E-Kredity: zimní s.:6
Způsob provedení zkoušky: zimní s.:
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neomezen / neomezen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Úroveň:  
Pro druh: bakalářské
Garant: Holub Jan prof. Ing. Ph.D.
Janoušek Jan doc. Ing. Ph.D.
Záměnnost : N500009
Termíny zkoušek   
Anotace -
Poslední úprava: Kubová Petra Ing. (02.01.2018)
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ů.
Výstupy studia předmětu -
Poslední úprava: Kubová Petra Ing. (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ů.

Literatura -
Poslední úprava: Kubová Petra Ing. (02.01.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.

Studijní opory -
Poslední úprava: Kubová Petra Ing. (02.01.2018)

https://edux.fit.cvut.cz/courses/BI-AAG/

(nutné přihlášení)

Sylabus -
Poslední úprava: Kubová Petra Ing. (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.

Studijní prerekvizity -
Poslední úprava: Kubová Petra Ing. (02.01.2018)

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

Podmínky zakončení předmětu (Další požadavky na studenta)
Poslední úprava: Svozil Daniel prof. Mgr. Ph.D. (07.02.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.

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