|
|
New Parallel and Regulated Automata and Grammars
Kučera, Jiří ; Průša, Daniel (oponent) ; Sawa, Zdeněk (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis introduces and studies four new language models with focus on regulation and parallelism in automata and grammars. First, state-synchronized automata systems , present systems consisting of a finite number of pushdown automata controlled by words of a control language over a set of states. Second, unlimited deep pushdown automata , are a modification of deep pushdown automata with no restrictions imposed on the depth of expansion on the pushdown. Third, jumping pure grammars , introduces jumping grammars with no nonterminal symbols. The last one, k#$-rewriting systems , extends #-rewriting systems with additional pushdown memory. The contents of this thesis are divided into three parts. The first part outlines the motivation for introduction of the studied language models and puts them into the context of related formal language theory areas. Furthermore, it gives an overview of the structure of the thesis, reviews fundamental notions of formal language theory and gives a survey of current knowledge related to the subject of research. The second part presents the core of this thesis. Here, formal definitions of all newly introduced language models are given and their expressive power is studied. Finally, this thesis is concluded with a summary of achieved theoretical results as well as related open problem areas, and an outline of the possibilities for further research along with a sketch of possible applications.
|
|
|
Syntaktická analýza založená na gramatických a automatových systémech
Šoustar, Jakub ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá syntaktickou analýzou s využitím systémů paralelně komunikujících zásobníkových automatů. Zejména se zaměřuje na dopady nedeterminismu v jednotlivých komponentách na celý systém. Také je představen návrh algoritmu pro převod některých paralelně komunikujících gramatických systémů na systémy paralelně komunikujících zásobníkových automatů. Získané poznatky jsou použity při návrhu a implementaci metody syntaktické analýzy.
|
|
|
Systémy formálních modelů a jejich aplikace
Čermák, Martin ; Lukáš, Roman (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce pojednává o automatových systémech jako o novém způsobu zpracování formálních jazyků. V textu jsou zmíněny čtyři modely. První z nich pracuje v sekvenčním módu. V jednom okamžiku počítá jediná komponenta systému. Druhý z nich pracuje v částečně paralelním módu. Zde během jednoho výpočetního kroku aktivně pracují buďto všechny, nebo pouze jediná komponenta systému. V posledních dvou modelech každý automat zpracovává svůj vlastní vstupní řetězec, přičemž jeho výpočet je řízen stavy, resp. přechody ostatních komponent. Stavy, resp. pravidla přechodů komponent mohou zapříčinit i tzv. blokaci, nebo odblokování dílčích automatů.
|
|
|
Nové verze automatových a gramatických systémů
Lichota, Lukáš ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá modifikáciou klasických gramatických systémov na báze bezkontextových gramatík a zavádza nové, modifikované lineárne gramatické systémy na báze gramatík lineárnych. Rovnako sa zaoberá podobnou modifikáciou v automatových systémoch, kde jednotlivé automaty odpovedajú svojou generatívnou silou lineárnym gramatikám, čo spĺňajú jednoobrátkové zásobníkové automaty. Práca ponúka taktiež pohľad na programovú realizáciu teoretických modelov navrhnutých v teoretickej časti a predstavuje dva programy pre syntaktickú analýzu založenú na nich.
|
|
|
New Parallel and Regulated Automata and Grammars
Kučera, Jiří ; Průša, Daniel (oponent) ; Sawa, Zdeněk (oponent) ; Meduna, Alexandr (vedoucí práce)
This thesis introduces and studies four new language models with focus on regulation and parallelism in automata and grammars. First, state-synchronized automata systems , present systems consisting of a finite number of pushdown automata controlled by words of a control language over a set of states. Second, unlimited deep pushdown automata , are a modification of deep pushdown automata with no restrictions imposed on the depth of expansion on the pushdown. Third, jumping pure grammars , introduces jumping grammars with no nonterminal symbols. The last one, k#$-rewriting systems , extends #-rewriting systems with additional pushdown memory. The contents of this thesis are divided into three parts. The first part outlines the motivation for introduction of the studied language models and puts them into the context of related formal language theory areas. Furthermore, it gives an overview of the structure of the thesis, reviews fundamental notions of formal language theory and gives a survey of current knowledge related to the subject of research. The second part presents the core of this thesis. Here, formal definitions of all newly introduced language models are given and their expressive power is studied. Finally, this thesis is concluded with a summary of achieved theoretical results as well as related open problem areas, and an outline of the possibilities for further research along with a sketch of possible applications.
|
|
|
Nové verze automatových a gramatických systémů
Lichota, Lukáš ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Táto práca sa zaoberá modifikáciou klasických gramatických systémov na báze bezkontextových gramatík a zavádza nové, modifikované lineárne gramatické systémy na báze gramatík lineárnych. Rovnako sa zaoberá podobnou modifikáciou v automatových systémoch, kde jednotlivé automaty odpovedajú svojou generatívnou silou lineárnym gramatikám, čo spĺňajú jednoobrátkové zásobníkové automaty. Práca ponúka taktiež pohľad na programovú realizáciu teoretických modelov navrhnutých v teoretickej časti a predstavuje dva programy pre syntaktickú analýzu založenú na nich.
|
|
|
Systémy formálních modelů a jejich aplikace
Čermák, Martin ; Lukáš, Roman (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce pojednává o automatových systémech jako o novém způsobu zpracování formálních jazyků. V textu jsou zmíněny čtyři modely. První z nich pracuje v sekvenčním módu. V jednom okamžiku počítá jediná komponenta systému. Druhý z nich pracuje v částečně paralelním módu. Zde během jednoho výpočetního kroku aktivně pracují buďto všechny, nebo pouze jediná komponenta systému. V posledních dvou modelech každý automat zpracovává svůj vlastní vstupní řetězec, přičemž jeho výpočet je řízen stavy, resp. přechody ostatních komponent. Stavy, resp. pravidla přechodů komponent mohou zapříčinit i tzv. blokaci, nebo odblokování dílčích automatů.
|
|
|
Syntaktická analýza založená na gramatických a automatových systémech
Šoustar, Jakub ; Kocman, Radim (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce se zabývá syntaktickou analýzou s využitím systémů paralelně komunikujících zásobníkových automatů. Zejména se zaměřuje na dopady nedeterminismu v jednotlivých komponentách na celý systém. Také je představen návrh algoritmu pro převod některých paralelně komunikujících gramatických systémů na systémy paralelně komunikujících zásobníkových automatů. Získané poznatky jsou použity při návrhu a implementaci metody syntaktické analýzy.
|
host ::
RSS.