Detail práce

Cestami řízené gramatiky

Diplomová práce Student: Adamec Ondřej Akademický rok: 2014/2015 Vedoucí: Křivka Zbyněk, Ing., Ph.D.
Název anglicky
Path-Controlled Grammars
Jazyk práce
český
Abstrakt

Tato diplomová práce se zabývá cestami řízenými gramatikami, gramatikami, které kladouomezení na cesty v derivačním stromě bezkontextové gramatiky. Cílem této diplomovépráce je tvorba algoritmu pro převod mezi cestami řízenými gramatikami a stavovými gramatikami,což je jiný typ řízené gramatiky. Dalším cílem je na základě tohoto převodníhoalgoritmu studovat vyjadřovací sílu cestami řízených gramatik. Převodní algoritmus jenaimplementován v C++ a testován na sadě cestami řízených gramatik. Složitost algoritmu,jak časová, tak prostorová, je diskutována. Také nástroj pro syntaktickou analýzucestami řízených gramatik je naimplementován. Složitost této analýzy je také diskutována.

Klíčová slova

cestami řízené gramatiky, maticové gramatiky, statové gramatiky, řízené gramatiky, formální jazyky, syntaktická analýza.

Ústav
Ústav informačních systémů FIT VUT v Brně
Studijní program
Informační technologie, obor Matematické metody v informačních technologiích
Soubory
Stav
obhájeno, hodnocení C
Obhajoba
24. června 2015
Oponent
Soukup Ondřej, Ing.
Průběh obhajoby

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm "C"

Otázky u obhajoby
  1. Zadání neurčuje konkrétní formální model, který má být výsledkem konverze. Byly zvažovány i jiné modely? Z jakého důvodu bylo výhodné zvolit právě stavové gramatiky?
  2. Zaměřte se na první a druhý řádek indukčního kroku na straně 15. Jedná se na obou řádcích o stejná x,a,y,m? Pokud ano, je tedy možné pro daný řetězec jazyka xay libovolně měnit délku sekvence následujících čtverců? Vysvětlete.
Komise
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT), předseda
Burget Radek, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Drahanský Martin, prof. Ing., Dipl.-Ing., Ph.D. (UITS FIT VUT), člen
Hrubý Martin, Ing., Ph.D. (UITS FIT VUT), člen
Rozinajová Viera, doc. Ing., Ph.D. (FIIT STU), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (UIFS FIT VUT), člen
Citace
ADAMEC, Ondřej. Cestami řízené gramatiky. Brno, 2015. Diplomová práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2015-06-24. Vedoucí práce Křivka Zbyněk. Dostupné z: https://www.fit.vut.cz/study/thesis/14737/
BibTeX 
@mastersthesis{FITMT14737,
    author = "Ond\v{r}ej Adamec",
    type = "Diplomov\'{a} pr\'{a}ce",
    title = "Cestami \v{r}\'{i}zen\'{e} gramatiky",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2015,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/14737/"
}

Závěrečné práce

Nahoru