PředmětyPředměty(verze: 948)
Předmět, akademický rok 2023/2024
  
Automaty a gramatiky - N500009
Anglický název: Automata and Grammars
Zajišťuje: ČVUT v Praze, Fakulta informačních technologií (500)
Fakulta: Vysoká škola chemicko-technologická v Praze
Platnost: od 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: neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Způsob výuky: prezenční
Úroveň:  
Je zajišťováno předmětem: B500005
Pro druh:  
Garant: Holub Jan prof. Ing. Ph.D.
Je záměnnost pro: B500005
Termíny zkoušek   Rozvrh   
Anotace -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)
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: Jirát Jiří Ing. Ph.D. (13.01.2014)

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: Jirát Jiří Ing. Ph.D. (09.01.2014)

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: Jirát Jiří Ing. Ph.D. (09.01.2014)

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

(nutné přihlášení)

Sylabus -
Poslední úprava: Jirát Jiří Ing. Ph.D. (09.01.2014)

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: Jirát Jiří Ing. Ph.D. (09.01.2014)

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

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 0.5 14
Práce na individuálním projektu 2 56
Příprava na zkoušku a její absolvování 1.1 30
Účast na seminářích 1 28
6 / 6 156 / 168
 
VŠCHT Praha