Počkejte prosím...
Data pro 2018/2019

Automaty a gramatiky

Kredity 6
Rozsah 2 / 2 / 0
Examinace Z+Zk
Jazyk výuky čeština
Úroveň bakalářský předmět
Garant prof. Ing. Jan Holub, Ph.D.

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ů.

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.

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.

VŠCHT Praha
Technická 5
166 28 Praha 6 – Dejvice
IČO: 60461373
DIČ: CZ60461373

Datová schránka: sp4j9ch

Copyright VŠCHT Praha 2014
Za informace odpovídá Oddělení komunikace, technický správce Výpočetní centrum
zobrazit plnou verzi