|
|
Vizualization of Automata Algorithms
Kuchyňka, Jiří ; Češka, Milan (oponent) ; Holík, Lukáš (vedoucí práce)
The goal of this thesis is to design and implement a generic system to visualize algorithms that operate over automata. The resulting system completely separates the part that is dedicated to generating data for visualization and the part that is dedicated to visualizing it. The system only specifies their communication interface. This thesis focuses on integrating such system into existing libraries in a way to minimize the requirements on the programmer to start visualizing the state of their algorithm. The thesis also briefly discusses the possibilities of using such a system to visualize the state of an algorithm while stepping through the program during debugging. The proposed system can be used for teaching, research, and practical applications in automata theory. In the future, the system could be extended with tools to visualize Turing machines and algorithms operating on them.
|
|
|
Prostředí pro podporu modelů formálních jazyků
Juda, Jan ; Kocman, Radim (oponent) ; Křivka, Zbyněk (vedoucí práce)
Cílem této práce je vytvořit podpůrné prostředí pro spouštění algoritmů a výpočet typických problémů na pokročilých modelech formálních jazyků. Toto prostředí je realizováno jako modulární aplikace s využitím OSGi rámce, u které autor dbá na snadnou integraci nových uživatelem definovaných modelů formálních jazyků a algoritmů pro tyto modely, a to bez nutnosti úprav či opětovného překladu ostatních částí prostředí včetně jeho jádra. Pro demonstrování svých možností podpůrné prostředí obsahuje implementaci konečného automatu, bezkontextové gramatiky, n-zásobníkového m-páskového automatu, obecného skákajícího konečného automatu, Watson-Crickova konečného automatu, problému členství a algoritmů obecně schopných řešit problém členství na automatech a gramatikách.
|
|
|
Dependability Assessment Based on SMC
Gajdošík, Róbert ; Lojda, Jakub (oponent) ; Strnadel, Josef (vedoucí práce)
The aim of this thesis is assessing dependability of computerized systems using modelling and simulation. After establishing basic nomenclature, research was performed on de- pendability metrics, fault taxonomy and dependability bolstering techniques. Afterwards, analytical solutions were explored to be used as a reference point. Next, multiple simulation tools were assessed and Uppaal SMC was chosen as the most suitable tool because of it’s timed automaton framework enriched with a query language and multiple Simulation Model Checking tools. Finally, systems describing multiple relevant situations were implemented and evaluated against both themselves and the analytically computed reference point.
|
|
| |
|
|
Nástroje pro experimenty s gramatikami a jazyky
Krejsa, Jiří ; Bednárek, David (vedoucí práce) ; Král, Jaroslav (oponent)
Hlavním cílem diplomové práce je návrh a implementace prostředí, které poskytne prostředky pro práci s gramatikami a jazyky. Prostředí je realizováno knihovnou, se kterou uživatel pracuje pomocí API. Knihovna umožňuje manipulovat s jazyky v podobě gramatiky nebo automatu, převádět jazyk mezi jeho různými reprezentacemi a testovat zda je gramatika regulární, lineární nebo LR(k) pro zvolené k. V případě porušení podmínek testované vlastnosti je nalezen protipříklad. Důraz je kladen na další rozšiřitelnost knihovny. Součástí práce je ukázková implementace využití knihovny. Knihovna i ukázka je napsána v jazyce C++.
|
|
|
Regulovaný syntaxí řízený překlad
Dvořák, Tomáš ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá formálním pohledem na regulovaný syntaxí řízený překlad. První část obsahuje formální základy teorie jazyků, jejich klasifikaci a analýzu. Jsou uvedeny příklady gramatik generující jazyky, které nejsou bezkontextové, především maticové gramatiky, gramatiky s nahodilým kontextem a programované gramatika. Jsou uvedeny konečné, zásobníkové, hluboké a regulované automaty. Formálně vymezuje převodníky a jejich roli v rámci formálního a syntaxí řízeného překladu. Zavádí regulované převodníky založené na regulovaných automatech. Jádrem práce je návrh algoritmů regulované syntaktické analýzy jako rozšíření tradičních algoritmů prediktivní syntaktické analýzy. Tyto algoritmy jsou navrženy pro všechny uvedené speciální typy gramatik. Závěr práce je věnován návrhu jazyka jako prostředku pro popis těchto gramatik a překladače těchto gramatik na kód syntaktického analyzátoru a jejich grafického analyzátoru.
|
|
|
Nástroje pro experimenty s gramatikami a jazyky
Krejsa, Jiří ; Král, Jaroslav (oponent) ; Bednárek, David (vedoucí práce)
Hlavním cílem diplomové práce je návrh a implementace prostředí, které poskytne prostředky pro práci s gramatikami a jazyky. Prostředí je realizováno knihovnou, se kterou uživatel pracuje pomocí API. Knihovna umožňuje manipulovat s jazyky v podobě gramatiky nebo automatu, převádět jazyk mezi jeho různými reprezentacemi a testovat zda je gramatika regulární, lineární nebo LR(k) pro zvolené k. V případě porušení podmínek testované vlastnosti je nalezen protipříklad. Důraz je kladen na další rozšiřitelnost knihovny. Součástí práce je ukázková implementace využití knihovny. Knihovna i ukázka je napsána v jazyce C++.
|
|
|
Formal Systems Based on Automata and Grammars
Čermák, Martin ; Rybička, Jiří (oponent) ; Šaloun, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
The present thesis continues with study of grammar and automata systems. First of all, it deals with regularly controlled CD grammar systems with phrase-structure grammars as components. Into these systems, three new derivation restrictions are placed and their effect on the generative power of these systems are investigated. Thereafter, this thesis defines two automata counterparts of canonical multi-generative nonterminal and rule synchronized grammar systems, generating vectors of strings, and it shows that these investigated systems are equivalent. Furthermore, this thesis generalizes definitions of these systems and establishes fundamental hierarchy of n-languages (sets of n-tuples of strings). In relation with these mentioned systems, automaton-grammar translating systems based upon finite automaton and context-free grammar are introduced and investigated as a mechanism for direct translating. At the end, in this thesis introduced automata systems are used as the core of parse-method based upon n-path-restricted tree-controlled grammars.
|
|
|
Nové verze skákajících automatů
Ošmera, Lubomír ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Cílem této bakalářské práce je návrh a výzkum nových verzí skákajících automatů, konkrétně se jedná o verze obecných skákajících automatů s jasně specifikovanými kritérii směru a velikosti skoku. Práce zkoumá jejich sílu v porovnání s ostatními typy automatů a odhaluje ekvivalentní modely gramatik. Důvodem vypracování této práce je výzkum a snaha o vylepšení některých vlastností obecného skákajícího automatu. Následně je v práci zváženo využití tohoto formálního prostředku za účelem zpracování určitého typu jazyků a využití v průběhu syntaktické analýzy.
|
|
|
Modifikované zásobníkové automaty
Hromádka, David ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí omezené Hromádkovy automaty jako rozšíření zásobníkových automatů. Toto rozšíření spočívá v~tom, že automat může za běhu vytvářet nové zásobníky, vkládat do nich symboly vstupní abecedy, spojovat je a porovnávat se vstupním řetězcem. Počet takto vytvořených zásobníků je omezen zvolenou konstantou n . Dále tato práce popisuje implementaci aplikace, která činnost těchto automatů realizuje a hledá posloupnost derivačních kroků, kterými určitý omezený Hromádkův automat přijme zadaný vstupní řetězec.
|
host ::
RSS.