Original title:
Transformace frontových gramatik
Translated title:
Transformation of Queue Grammars
Authors:
Holas, David ; Regéciová, Dominika (referee) ; Křivka, Zbyněk (advisor) Document type: Master’s theses
Year:
2023
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Diplomová práce je rozdělena do dvou částí. První část spočívá v opravě chyby v algoritmickém převodu frontové gramatiky do 1. normální formy navrženém jiném odborném článku. Algoritmus byl analyzován a úspěšně opraven. Druhá část se zabývá návrhem nové transformace na gramatiky s rozptýleným kontextem s omezenou popisnou složitostí. Práce obsahuje důkaz její korektnosti a studium její složitosti. Byla vytvořena konzolová aplikace, která pomáhá automaticky analyzovat příslušné transformace.
The master thesis is divided into two parts. First part focuses on fixing incorrect transformation algorithm of queue grammar into a first normal form proposed in other paper. The algorithm was analysed and successfully corrected. Second part focuses on proposing a new tranformation to scattered context grammars with reduced descriptional complexity. The thesis contains a proof of its correctness and contains its complexity analysis. Console application was created to help analyze the respective transformations.
Keywords:
first normal form; normalization; normalzation; Queue grammars; reduced descriptional complexity; scattered context grammars; second normal form; single context-sensitive rule; Swift language.; tranformation; 1. normální forma; 2. normální forma; Frontové gramatiky; gramatiky s rozptýleným kontextem; jazyk Swift.; jedno kontextové pravidlo; normalizace; omezení popisné složitosti; transformace
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/211897