Original title:
Částečně paralelní hluboké zásobníkové převodníky a jejich aplikace
Translated title:
Semi-Parallel Deep Pushdown Transducers and Their Applications
Authors:
Putala, Marek ; Dolejška, Daniel (referee) ; Meduna, Alexandr (advisor) Document type: Bachelor's theses
Year:
2023
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Cílem této práce bylo seznámit se s hlubokými zásobníkovými automaty a na základě získaných znalostí dále navrhnout, formálně definovat a implementovat částečně paralelní hluboký zásobníkový převodník. Jedná se o rozšíření hlubokých zásobníkových převodníků, které je na zásobníku schopné v jednom kroku přistupovat k non-terminálním symbolům současně. S vhodně zvolenou konfigurací ve formě pravidel mohou zpracovat vstupní řetězec s menším množstvím přechodů, a tím pádem mají oproti hlubokým zásobníkovým převodníkům vyšší rychlost.
The goal of this work was to become familiar with deep stack automata and, based on the acquired knowledge, to further design, formally define and implement a partially parallel deep stack transducer. It is an extension of deep stack transducer that is capable of accessing non-terminal symbols simultaneously on the stack in one step. With a suitably chosen configuration in the form of rules, they can process the input string with fewer transitions and therefore have a higher speed compared to deep stack transducer.
Keywords:
automata; context-free grammar; deep pushdown transducer; finite automata; formal language; grammar; pushdown automata; pushdown transducer; semi-parallel deep pushdown transducer; state grammar; automat; bezkontextová gramatika; formální jazyk; gramatika; hluboký zásobníkový převodník; konečný automat; převodník; stavová gramatika; zásobníkový automat; zásobníkový převodník; částečně paralelní hluboký zásobníkový převodník
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/211031