|
|
New Versions of Jumping Automata
Ošmera, Lubomír ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
The main goal of this thesis is introduction and investigation of extended version of jumping automata. These versions are specified by strictly size and direction of jump. This thesis examine their power and perform comparison with other automata types. Also there are shown equivalent grammar models. Main motivation for this thesis are research and effort to improve some features of general jumping finite automata. This work consider using this automata types for specific language families and syntactic analysis process.
|
|
|
Semi-Parallel Deep Pushdown Automata
Ševčík, Miroslav ; Zámečníková, Eva (referee) ; Meduna, Alexandr (advisor)
This work introduces semi-parallel deep pushdown automata as an extension of sequential deep pushdown automata. Unlike the sequential automaton, a semi-parallel one is able to make expansions of n nonterminal symbols on the pushdown top simultaneously. These automata, same as sequential deep pushdown automata, define the family of languages generated by n-limited state grammars. The advantage of semi-parallel deep pushdown automata lies in higher speed. This work also describes the implementation of an aplication that simulates operation of these automata.
|
|
|
Regulated Syntax-Directed Translation
Dvořák, Tomáš ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis deals with formal and syntax directed translation. This thesis contains theoretical part, which defines regular, context free, context sensitive and recursively enumerable languages a grammar. There are given examples of grammars which are able to generate languages that are not context free. Covered by this thesis are matrix grammars, random context grammars and programed grammars. Researched are also finite, pushdown, deep and regular automata, transducers and their part within format syntax directed translation. This project also defines regular transducers based as regulated automata. Thesis defines regulated methods of syntax analysis based on predictive parsers. These methods cover analysis of studied regulated grammars. The final part of this thesis describes new language capable of effective description of these grammars and compiler producing parser code for these grammars written in this new language and their graphical analyzer.
|
|
|
Formal Systems Based on Automata and Grammars
Čermák, Martin ; Rybička, Jiří (referee) ; Šaloun, Petr (referee) ; Meduna, Alexandr (advisor)
Tyto teze navazují na studium gramatických a automatových systémů. Na začátku, práce pojednává o regulárně řízených CD gramatických systémech využívající frázově strukturované gramatiky jako komponenty. Do systémů jsou zavedena tři nová omezení na derivacích a je studován jejich vliv na vyjadřovací sílu těchto systémů. Poté, tato práce definuje dva automatové protějšky ke kanonickým multi-generatiním nonterminálem a pravi\-dlově synchronizovyným gramatickým systemům, generujících vektory řetězců, a ukazuje, že všechny tyto vyšetřované systemy si jsou vzájemně ekvivalentní. Dále táto práce tyto systémy zobecňuje a zakládá fundamentalní hierarchii n-jazyků (množin n-tic řetězců). V~souvislosti se zavedenými systémy tyto teze zavádí automatově-gramatický převodník založený na konečném automatu a bezkontextové gramatice. Tento převodník je pak studovaný a použitý jako nástroj přímého překladu. V~poslední části jsou v této práci zavedené automatové systémy jádrem pársovací metody založené na stromově řízených gramatikách s n omezenými cestami.
|
|
|
Modified Pushdown Automata
Hromádka, David ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This work introduces limited Hromádka's automata as an extension of classical pushdown automata. This extension means that the automaton is able to create new pushdowns, insert input symbols into them, join them and compare with the input string in run time. The number of such pushdowns is limited by choosen constant n . This work also describes the implementation of the application, that realizes the activity of this automata and is looking for the sequence of derivational steps, by which the automaton accepts the input string.
|
|
|
Systems that Combine Automata and Grammars
Petřík, Patrik ; Křivka, Zbyněk (referee) ; Meduna, Alexandr (advisor)
This work deals with Systems that combine automata and grammars. We investigate their properties compared with grammar systems and automaton systems. Work is focused on systems, which components are finite state automata, right linear grammars, pushdown automata or context free grammars. We also investigate usage of these systems in compilers.
|
|
|
Vizualization of Automata Algorithms
Kuchyňka, Jiří ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Tato práce se zabývá návrhem a implementací generického systému k vizualizaci algoritmů, které pracují nad automaty. Výsledný systém zcela odděluje část, která se věnuje generování dat k vizualizaci a část, která se věnuje vizualizování. Systém pouze určuje jejich komunikační rozhraní. Práce se zaměřuje na integraci takovéhoto systému do existujících knihoven takovým způsobem, aby byly minimalizovány požadavky na programátora, k tomu aby mohl vizualizovat stav svého algoritmu. Práce se také zkráceně věnuje možnostem využití tohoto systému k vizualizaci stavu algoritmu při krokování programem během ledění. Navržený systém může být použit pro výuku, výzkum a praktické aplikace v oblasti teorie automatů. V budoucnu by mohl být systém rozšířen o nástroje k vizualizaci turingových strojů a algoritmů pracujících nad nimi.
|
|
|
Environment for Formal Language Models Support
Juda, Jan ; Kocman, Radim (referee) ; Křivka, Zbyněk (advisor)
The goal of this thesis is to create an environment that supports advanced formal language models including the computation of algorithms for typical problems. This environment is developed as a modular application using OSGi framework, that focuses on easy integration of new user-defined formal language models and algorithms for these models. The modularity provides the possibility to integrate a new user-defined language model and the corresponding algorithms without necessity to recompile the rest of the system. Therefore, a new module can be seamlessly plugged in into the system. As a demonstration of its capabilities, the environment supports the models of finite automata, context free grammars, n-pushdown m-tape automata, general jumping finite automata, Watson-Crick finite automata, the membership problem and algorithms that are generally able to solve membership problem on automata and grammars.
|
|
|
Dependability Assessment Based on SMC
Gajdošík, Róbert ; Lojda, Jakub (referee) ; Strnadel, Josef (advisor)
Cieľom tejto práce bolo vyhodnotiť ukazalete spoľahlivosti výpočtových systémov. V pr- vom rade bola založená terminológia ktorá vysvetľuje základné pojmy ohľadom štatistiky and spoľahlivosti. Ďalej boli v tomto kroku preskúmané typy a vlastnosti chýb ktoré sa v takýchto systémoch vyskytujú, a techniky ktoré sa dajú využit na ich potlačenie alebo zmiernenie ich dopadu na fungovanie systému. V ďalšom kroku boli vysvetlené základné koncepty ohľadom modelovania a simulácie ako aj krátky nahľad do presností jednotlivých techník ktoré boli zvažované ako možnosti ktoré by boli použiteľné pri samotnom pro- cese generovania dát. Po rozhodnutí ísť cestou štatistickej simulácie boli v ďalšom kroku zavedené metódy pre generovanie dát analytickým spôsobom ktoré slúžia na overenie dát vygenerovaných štatistickými simuláciami, do úrovne kde je ešte možné sa k nim dostať re- latívne jednoduchými výpočtami. Nasleduje prehľad nástrojov na implementáciu modelov našich systémov, ich výhody a nevýhody a miera použiteľnosti. V ďalšich krokoch boli vo vybranom nástroji Uppaal SMC naimplementované niektoré vybrané systémy a situácie na základe časovych automatov, a následne boli vyhodnotené oproti iným metódam zlepšenia spoľahlivosti ako aj oproti analyticky dosiahnutým dátam. Práca končí zavermi ktoré boli vyvodené z testovacích dát.
|
|
| |
guest ::
