|
|
A Combination of Automata and Grammars
Kučera, Jiří ; Horáček, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
In this work, a new systems of formal models, called state-synchronized automata systems of degree n , were introduced and studied. The computation in presented automata systems is controlled by words from finite control language, where every word from control language is a sequence of states. Furthermore were studied the computational power of these systems. The practical use of introduced systems was demonstrated on example of natural language translation and on example of parallel compiling.
|
|
| |
|
|
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.
|
|
|
Částečně paralelní hluboké zásobníkové automaty
Ševčík, Miroslav ; Zámečníková, Eva (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí částečně paralelní hluboké zásobníkové automaty jako rozšíření sekvenčních hlubokých zásobníkových automatů. Toto rozšíření spočívá v tom, že oproti sekvenční verzi je automat schopen provést expanzi n nejvýše položených nonterminálních symbolů na zásobníků současně. Tyto automaty jsou schopné rozpoznat třídu jazyků generovanou n-omezenými stavovými gramatikami stejně jako sekvenční hluboké zásobníkové automaty. Výhoda částečně paralelních hlubokých zásobníkových automatů je ale ve vyšší rychlosti. Dále je v této práci popsána implementace aplikace, která simuluje činnost těchto automatů.
|
|
|
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.
|
|
|
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.
|
|
|
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.
|
|
|
Systémy kombinující automaty a gramatiky
Petřík, Patrik ; Křivka, Zbyněk (oponent) ; Meduna, Alexandr (vedoucí práce)
V této práci jsou definovány a studovány systémy kombinující gramatiky a automaty. Jsou zkoumány jejich vlastnosti s ohledem na již známé gramatické či automatové systémy a to především pro komponenty síly regulárních jazyků a komponenty síly bezkontextových jazyků. V rámci práce je vytvořen i skript simulující jeden ze studovaných systémů po praktické stránce.
|
|
|
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.
|
host ::
RSS.