Automaty a gramatiky

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

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

Požadavky:

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

Osnova přednášek:

1. Motivace pro studium formálních jazyků. Základní pojmy (jazyk, abeceda, gramatika, automat), Chomského hierarchie. Deterministické a nedeterministické konečné automaty (DKA a NKA), NKA s epsilon přechody.

2. Operace s automaty (převod na NKA bez epsilon přechodů, na DKA, minimalizace), průnik, sjednocení. Programová realizace DKA a NKA, obvodová realizace.

3. Rozšíření o překlad, Mealey, Moore, převody. Operace s regulárními gramatikami, převody na KA.

4. Regulární výrazy, převody mezi regulárními výrazy, konečnými automaty a regulárními gramatikami, Kleenova věta. Principy využití regulárních výrazů v UNIXu (grep, egrep, perl, PHP, ...).

5. Konečný automat jako lexikální analyzátor, lex/flex generátory. Vlastnosti regulárních jazyků (pumping lemma, Nerodova věta).

6. Jazyky bezkontextové, zasobníkový automat. Analýza bezkontextových jazyků (nedeterministická versus deterministická).

7. Jazyky kontextové a neomezené, Turingův stroj.

Osnova cvičení:

1. Ukázky formálních jazyků. Intuitivní návrh gramatik pro jazyky zadané množinově. Odhad umístění jazyka v Chomského hierarchii. Intuitivní návrh konečných automatů (DKA, NKA, s epsilon-přechody) pro zadaný jazyk. Převody a kompozice KA. Implementace KA. Návrh KA s výstupní funkcí a jeho implementace.

2. Převody gramatik na KA a zpět. Návrh, úpravy a převody regulárních výrazů. Využití regulárních výrazů pro řešení úloh ze zpracování textu (např. sh, grep, sed, perl). Návrh a implementace lexikálního analyzátoru. Klasifikace jazyků.

3. Příklady bezkontextových jazyků, návrh zásobníkových automatů. Ukázky deterministické analýzy bezkontextových jazyků (např. LL, yacc, bison). Příklady kontextových a neomezených jazyků, návrh gramatik a Turingových strojů.

Cíle studia:

Předmět si klade za cíl seznámit studenty s konečnými automaty, regulárními výrazy, gramatikami a překladovými konečnými automaty s důrazem na praktické využití. Dále pak seznámí studenta s třídou bezkontextových jazyků, základním použitím zásobníkových automatů a s hierarchií jazyků pro jeho snazší orientaci v problematice. Znalosti získané v tomto předmětu naleznou uplatnění při návrhu algoritmů pro vyhledávání vzorků, kompresi dat, překlad, jednoduchou syntaktickou analýzu a při návrhu číslicových obvodů.

Studijní materiály:

Melichar, B. ''Jazyky a překlady''. Praha: ČVUT, 1996. ISBN 80-01-01511-4.

Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. ''Compilers: Principles, Techniques, and Tools (2nd Edition)''. Addison Wesley, 2007. ISBN 0321486811.

Kozen, D. C. ''Automata and Computability''. Springer, 1997. ISBN 0387949070.

Melichar, B., Holub, J., Mužátko, P. ''Languages and Translations''. Praha: Publishing House of CTU, 1997. ISBN 80-01-01692-7.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BIK-AAG/

Další informace:

https://courses.fit.cvut.cz/BIK-AAG/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, kombi., 2015 - 2020 (povinný předmět programu)
• Bc. obor Bezpečnost a informační technologie, kombi., 2015 - 2019 (povinný předmět programu)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, kombi., 2015 - 2020 (povinný předmět programu)
• Bc. obor Bezpečnost a informační technologie, kombinovaná forma studia, 2020 (povinný předmět programu)