PředmětyPředměty(verze: 965)
Předmět, akademický rok 2019/2020
  
Automaty a gramatiky - B500005
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 2019 do 2019
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
Stav předmětu: nevyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Úroveň:  
Garant: Holub Jan prof. Ing. Ph.D.
Janoušek Jan doc. Ing. Ph.D.
Záměnnost : N500009
Termíny zkoušek   Rozvrh   
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 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)
Podmínky zakončení předmětu (Další požadavky na studenta)

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)
Literatura -

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)
Sylabus -

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)
Studijní opory -

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

(nutné přihlášení)

Poslední úprava: Kubová Petra (02.01.2018)
Výsledky učení -

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)
Studijní prerekvizity -

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

 
VŠCHT Praha