Original title:
Demonstrace rozptýlených gramatik s jediným kontextovým pravidlem
Translated title:
Demonstration of Scattered Context Grammars with Single Context-Sensitive Rule
Authors:
Holas, David ; Klobučníková, Dominika (referee) ; Křivka, Zbyněk (advisor) Document type: Bachelor's theses
Year:
2021
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Práce se zabývá tvorbou aplikace, která ze zadané frontové gramatiky konstruuje gramatiku s rozptýleným kontextem a jedním kontextovým pravidlem, derivuje v~ní zadaný řetězec a celý proces prezentuje uživateli. K derivaci řetězců byla navržena heuristika, která snižuje počet aplikovatelných pravidel v každé větné formě. Uživatel může ovlivnit průběh derivace ručním výběrem pravidel. Průběh derivace je vypisován v podobě čistého textu nebo HTML dokumentu. Byly odhaleny dvě chyby v teoretickém podkladu práce, jmenovitě v převodu frontové gramatiky do 1. normální formy a v konstrukci gramatik s rozptýleným kontextem a jedním kontextovým pravidlem. V práci se podařilo nalézt částečné řešení druhého problému, které je implementováno v aplikaci.
The goal is to create an application that constructs scattered context grammars with single context-sensitive rule from queue grammars, and derives strings using them. The application presents the whole process to user in form of plain text or HTML. In order to derive strings, the heuristic is used to reduce the number of applicable rules in each sentential form. Applicable rules can be selected manually by the user in order to alter derivation process. Two errors were discovered in underlying theory of thesis. Specifically in transformation of queue grammars into first normal form and the construction of scattered context grammars with single context-sensitive rule. A partial solution to the second error was found and is implemented in application.
Keywords:
C language; demonstration; non-context-free production; normal forms; queue grammars; Scattered context grammars; state space search.; string derivation; demonstrace; derivace řetězců; frontové gramatiky; Gramatiky s rozptýleným kontextem; jazyk C; kontextové pravidlo; normální formy; prohledávání stavového prostoru.
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/199461