|
| |
|
|
New Versions of Pushdown Automata
Genčúrová, Ľubica ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis investigates multi pushdown automata and introduces their new modifications based on deep pushdown. The first modification is Input driven multi deep pushdown automata, which has several deep pushdown lists and the current input symbol determines whether the automaton performs a push operation, a pop operation, an expansion operation or does not touch the stack. The second introduced modification is Regulated pushdown automata by deep pushdown. In addition to ordinary pushdowns, this version contains deep pushdown, which is used to generate the control language. This thesis proves, that the acceptance power of the described variants is equal to the accepting power of Turing machines. This thesis also contains view on program realisation of theoretical models, which were described in the theoretical part and introduces a library for the syntax analysis, which is based on it.
|
|
|
Modified Deep Pushdown Automata
Škvařilová, Radka ; Horáček, Petr (referee) ; Meduna, Alexandr (advisor)
This thesis introduce two new modifications of deep pushdown automata - stateless deep pushdown automata and parallel deep pushdown automata. In theoretical part of this thesis is formal definition and research into power of these modification. Practical part consists of an implementation of simple automata program.
|
|
|
Deep Syntax-Directed Translation
Senko, Jozef ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
This thesis is a continuation of my bachelor thesis, which is dedicated to syntax analysis based on deep pushdown automata. In theorical part of this thesis is defined everything fundamental for this work, for example deep syntax-directed translation, pushdown automata, deep pushdown automata, finite transducer and deep pushdown transducer. The second part of this thesis is dedicated to the educational program for students of IFJ. In this part is defined strucure of this program and its parts. All part of program are analyzed from a theoretical and practical point of view.
|
|
|
Detecting JavaScript Code with Known Vulnerabilites
Randýsek, Vojtěch ; Jeřábek, Kamil (referee) ; Polčák, Libor (advisor)
This thesis deals with the detection of vulnerable JavaScript libraries and NPM packages. Based on existing studies, it summarizes the technological core of the Node.js platform and further focuses on selected vulnerabilities of the NPM system and existing means of protection. A Chrome browser extension able to detect and fix JavaScript code with known vulnerabilities on the web browser had been introduced. The tool was tested in a crawl of 50 000 websites. 8 129 vulnerable scripts were detected. The extension has been published to the Chrome Web Store as JS Vulnerability Detector .
|
|
|
Parallel Deep Pushdown Automata
Solár, Peter ; Křivka, Zbyněk (referee) ; Meduna, Alexandr (advisor)
This thesis introduces parallel deep pushdown automata as the parallel version of the deep pushdown automata. They are based on the rules, where the automaton can expand n topmost non-terminals in only one derivation step if there are enough non-terminals on the pushdown. The main advantage rests in a fact, that parallel automaton can makde a decission faster.
|
|
|
Alternative Versions of Deep Pushdown Automata and Their Applications
Klembara, Radovan ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
The goal of this thesis is to design new versions of deep pushdown automata, their analysis and aplication in informatics. In this thesis I present two new versions of automata. The idea behind modificatons is to add parallel processing of expansive transitions. The first version differs from second one by variable number of expansive transitions in each parallel step. For each new version I have created algorithms, which can be used to convert these versions to basic deep pushdown automata. Furhtermore I have created algorithms for converting basic deep pushdown automata back to these new versions. Proposed alternative versions of deep pushdown automata are faster than their basic version thanks to the paralelism. Through their analysis I have found out that their strength is same as strength of basic deep pushdown automata. For easier conversion between automata I have programmed console application, which implements proposed conversion algorithms. Solution of this thesis allows designing parallel version of deep pushdown automaton instead of basic deep pushdown automaton, that can result in faster and more efective design. Created automaton then can be easily converted via algorithm to basic version.
|
|
|
Semi-Parallel Deep Pushdown Transducers and Their Applications
Putala, Marek ; Dolejška, Daniel (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
Detecting JavaScript Code with Known Vulnerabilites
Randýsek, Vojtěch ; Jeřábek, Kamil (referee) ; Polčák, Libor (advisor)
This thesis deals with the detection of vulnerable JavaScript libraries and NPM packages. Based on existing studies, it summarizes the technological core of the Node.js platform and further focuses on selected vulnerabilities of the NPM system and existing means of protection. A Chrome browser extension able to detect and fix JavaScript code with known vulnerabilities on the web browser had been introduced. The tool was tested in a crawl of 50 000 websites. 8 129 vulnerable scripts were detected. The extension has been published to the Chrome Web Store as JS Vulnerability Detector .
|
|
|
New Parallel and Regulated Automata and Grammars
Kučera, Jiří ; Průša, Daniel (referee) ; Sawa, Zdeněk (referee) ; Meduna, Alexandr (advisor)
Tato práce zkoumá a zavádí čtyři nové jazykové modely se zaměřením na regulované a paralelní verze automatů a gramatik. První z modelů, stavově synchronizované systémy automatů , zavádí systémy složené z konečného počtu zásobníkových automatů jejichž činnost je řízena slovy z řídícího jazyka nad množinou stavů. Druhý model, neomezené hluboké zásobníkové automaty , je variantou hlubokých zásobníkových automatů z nichž bylo sejmuto omezení kladené na hloubku expanze na zásobníku. Třetí model, skákající čisté gramatiky , zavádí skákající gramatiky bez neterminálních symbolů. Poslední model, k#$-přepisující systémy , rozšiřuje #-přepisující systémy o přídavnou zásobníkovou paměť. Text této práce je členěn do tří částí. První část uvádí motivaci k zavedení studovaných jazykových modelů a zasazuje je do kontextu souvisejících oblastí teorie formálních jazyků. Je zde také uveden přehled o celkové organizaci práce, základních pojmů teorie formálních jazyků a současných poznatků souvisejících s předmětem výzkumu. Druhá část tvoří jádro této práce. Jsou v ní formálně definovány všechny nově zavedené jazykové modely a studována jejich vyjadřovací síla. Poslední část uzavírá tuto práci souhrnem získaných teoretických výsledků společně se souvisejícími otevřenými problémy a nastiňuje cesty dalšího výzkumu spolu s výhledy na možná využití.
|
guest ::
