|
|
Demonstration of Scattered Context Grammars with Single Context-Sensitive Rule
Holas, David ; Klobučníková, Dominika (referee) ; Křivka, Zbyněk (advisor)
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.
|
|
| |
|
|
A Restriction of Sentetial Forms of of Scattered Context Grammars
Šimáček, Jiří ; Masopust, Tomáš (referee) ; Meduna, Alexandr (advisor)
This work introduces and discusses generalized scattered context grammars that are based upon sequences of productions whose left-hand sides are formed by nonterminal strings, not just single nonterminals. It places two restrictions on the derivations in these grammars. More specifically, let k be a constant. The first restriction requires that rewriting all symbols occurs within the first k symbols of the first continuous block of nonterminals in the sentential form during every derivation step. The other restriction defines the derivations over sentential forms containing no more than k occurrences of nonterminals. As its main result, the thesis demonstrates that both restrictions decrease the generative power of these grammars to the power of context-free grammars.
|
|
|
New Versions of Classical Automata and Grammars
Soukup, Ondřej ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
Tato diplomová práce se zabývá zkoumáním nových verzí automatů a gramatik a je proto rozdělena do dvou částí. První část definuje a studuje čisté více zásobníkové automaty a navíc zavádí úplná uspořádání nad jejich zásobníky nebo zásobníkovými symboly. Práce dokazuje, že zavedená omezení snižují vyjadřovací sílu automatů. Ve druhé části práce jsou definovány a popsány nové derivační módy gramatik s rozptýleným kontextem, které zobecňují relaci přímé derivace. Je dokázáno, že jejich použití nesnižuje vyjadřovací sílu gramatik.
|
|
|
Retargetable Analysis of Machine Code
Křoustek, Jakub ; Janoušek, Jan (referee) ; Návrat,, Pavol (referee) ; Kolář, Dušan (advisor)
Analýza softwaru je metodologie, jejímž účelem je analyzovat chování daného programu. Jednotlivé metody této analýzy je možné využít i v dalších oborech, jako je zpětné inženýrství, migrace kódu apod. V této práci se zaměříme na analýzu strojového kódu, na zjištění nedostatků existujících metod a na návrh metod nových, které umožní rychlou a přesnou rekonfigurovatelnou analýzu kódu (tj. budou nezávislé na konkrétní cílové platformě). Zkoumány budou dva typy analýz - dynamická (tj. analýza za běhu aplikace) a statická (tj. analýza aplikace bez jejího spuštění). Přínos této práce v rámci dynamické analýzy je realizován jako rekonfigurovatelný ladicí nástroj a dále jako dva typy tzv. rekonfigurovatelného translátovaného simulátoru. Přínos v rámci statické analýzy spočívá v navržení a implementování rekonfigurovatelného zpětného překladače, který slouží pro transformaci strojového kódu zpět do vysokoúrovňové reprezentace. Všechny tyto nástroje jsou založeny na nových metodách navržených autorem této práce. Na základě experimentálních výsledků a ohlasů od uživatelů je možné usuzovat, že tyto nástroje jsou plně srovnatelné s existujícími (komerčními) nástroji a nezřídka dosahují i lepších výsledků.
|
|
|
Formal Models of Distributed Computation
Soukup, Ondřej ; Horváth,, Géza (referee) ; Rogalewicz, Adam (referee) ; Meduna, Alexandr (advisor)
Tato disertační práce představuje derivační stromy několika různých typů gramatik ve zobecněné Kurodově normální formě; jmenovitě obecné a regulárně řízené gramatiky, gramatiky s rozptýleným kontextem a spolupracující distribuované gramatické systémy. Definuje jednoduché stromové rysy založené na kontextových vlastnostech jednotlivých diskutovaných gramatik a dokazuje, že pokud existuje limitující konstanta k taková, že každá věta generovaného jazyka L odpovídá řetězci listových uzlů derivačního stromu, ve kterém je výskyt definovaných stromových rysů omezen konstantou k, jazyk L je ve skutečnosti bezkontextový. Tato práce dále ukazuje, že dosažený výsledek představuje silný nástroj důkazu bezkontextovosti jazyka. Vše je doplněno příklady praktického využití nástroje.
|
|
|
Parsing Based on Scattered Context Grammars
Horníček, Ondřej ; Solár, Peter (referee) ; Zámečníková, Eva (advisor)
This work deals with new possibilities in parsing based on advanced formal models, specifically using scattered context grammars in syntactic analysis. Context-sensitive language was created for comparing different methods of syntactic analysis, where these grammars are used. In conclusion is discussed possible use in practise, paralell parsing, pros and cons and further investigation.
|
|
|
Formal Models and Their Applications in Music
Makiš, Jozef ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
Main subject of this study are different kinds of formal models. We discuss which of them could be applied in music. Those that are applied are scattered context grammars and absolutely unlimited deep pushdown automata. They are applied in music structure as theme and variations. The main topic of a song is the theme, and variations diversify it. Resulting algorithm is based on compilation of a LL scattered context grammar. This algorithm shows how we can generate variations.
|
|
|
Transformation of Queue Grammars
Holas, David ; Regéciová, Dominika (referee) ; Křivka, Zbyněk (advisor)
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.
|
|
|
Formal Models and Their Applications in Music
Makiš, Jozef ; Tomko, Martin (referee) ; Meduna, Alexandr (advisor)
Main subject of this study are different kinds of formal models. We discuss which of them could be applied in music. Those that are applied are scattered context grammars and absolutely unlimited deep pushdown automata. They are applied in music structure as theme and variations. The main topic of a song is the theme, and variations diversify it. Resulting algorithm is based on compilation of a LL scattered context grammar. This algorithm shows how we can generate variations.
|
guest ::
