|
|
Graphical Simulation of Finite Automata
Šrajer, Roman ; Goldefus, Filip (referee) ; Čermák, Martin (advisor)
This Bachelor's Thesis is about the theory of converting regular expression to finate state machine and vice versa. The goal of practical part is to make web application that performs these coversions and do simulation for input string. For converting automata into regular expression it is used the algebraic method which is based on making an equation system to be solved. I have chosen Java as programming language and Java Applet and Java Web Start as technologies that make possible to access the application through the web page. The possibilities like working with three types of automata views, saving atomatons into XML and intuitively creating own automatons are the important part of the application.
|
|
|
Language Version Tools for Web Portal of BUT
Pavlíček, Milan ; Burget, Radek (referee) ; Marušinec, Jaromír (advisor)
The main purpose of this master's thesis is to create language version tools for web Portal of BUT. There are possibilities of applications using databases or without them. The next part of the thesis analyses current situation of the web Portal of BUT. I described individually servers, tools and mainly solution ensuring multilingual sites. Thereinafter I attend to design and implementation of required system. This system consists of some single scripts and web applications for web developers and translators. Finally I will describe the procedure of integration of this system to current web Portal of BUT.
|
|
|
Algorithm Database of Digital Audio Signal Processing with Automatic Classification and Searching using Web Interface
Kouba, Petr ; Sysel, Petr (referee) ; Schimmel, Jiří (advisor)
The aim of the bachelor was to design a database structure for classification source code and implementations of digital audio effects algorithms. Classification criteria for these algorithms are described in the thesis. A new project can be added to the database using web form or via of the automatic classification. The automatic classification is called a function for automatic recognition information in source files. For this purpose a format of saving catalog information into the source file was designed. These saved data can be further recognized by the suitable algorithm which utilizes PHP standard functions and then they inserted into the database. The saved projects can be searched by the project name, author’s name, the project description, or the criteria described in the introduction of this thesis.
|
|
|
Beat Grep with Counters, Challenge
Horký, Michal ; Češka, Milan (referee) ; Holík, Lukáš (advisor)
Vyhledávání regulárních výrazů má ve vývoji softwaru nezastupitelné místo. Rychlost vyhledávání může ovlivnit použitelnost softwaru, a proto je na ni kladen velký důraz. Pro určité druhy regulárních výrazů mají standardní přístupy pro vyhledávání vysokou složitost. Kvůli tomu jsou náchylné k útokům založeným na vysoké náročnosti vyhledávání regulárních výrazů (takzvané ReDoS útoky). Regulární výrazy s omezeným opakováním, které se v praxi často vyskytují, jsou jedním z těchto druhů. Efektivní reprezentace a rychlé vyhledávání těchto regulárních výrazů je možné s použítím automatu s čítači. V této práci představujeme implementaci vyhledávání regulárních výrazů založeném na automatech s čítači v C++. Vyhledávání je implementováno v rámci RE2, rychlé moderní knihovny pro vyhledávání regulárních výrazů. V práci jsme provedli experimenty na v praxi používaných regulárních výrazech. Výsledky experimentů ukázaly, že implementace v rámci nástroje RE2 je rychleší než původní implementace v jazyce C#.
|
|
|
Construction of Effective Automata for Regex Matching in HW
Frejlach, Jakub ; Havlena, Vojtěch (referee) ; Češka, Milan (advisor)
This thesis is motivated by the application of REs in domains requiring fast matching such has deep packet inspections. To ensure sufficient speed a HW acceleration is typically employed. During the acceleration, REs are in the form of NFA synthesized on FPGA. Although HW acceleration solves the speed problems, it suffers from increased consumption of the FPGA components, specifically LUT. The goal of this thesis is to design, implement and experimentally evaluate heuristic method for approximation of FA in context of HW accelerated RE matching. The purpose of this approximation is to lower consumption of LUT components during FPGA synthesis. The key idea of the method is to add some transitions allowing to construct a smaller number of character classes and thus to reduce the number of LUT implementing the transition relation while reducing the error by modifying only less significant parts of FA. Proposed method together with evaluation pipeline is implemented in TOFA tool. Technique was evaluated on both synthetic and real data. Results of experiments shows, that transitional approximation works especially well on automatas with large number of equivalence character classes.
|
|
|
OPTIMIZATION OF ALGORITHMS AND DATA STRUCTURES FOR REGULAR EXPRESSION MATCHING USING FPGA TECHNOLOGY
Kaštil, Jan ; Plíva, Zdeněk (referee) ; Vlček, Karel (referee) ; Kotásek, Zdeněk (advisor)
Disertační práce se zabývá rychlým vyhledáváním regulárních výrazů v síťovém provozu s použitím technologie FPGA. Vyhledávání regulárních výrazů v síťovém provozu je výpočetně náročnou operací využívanou převážně v oblasti síťové bezpečnosti a v oblasti monitorování provozu vysokorychlostních počítačových sítí. Současná řešení neumožňují dosáhnout požadovaných multigigabitových propustností při dodržení všech požadavků, které jsou na vyhledávací jednotky kladeny. Nejvyšších propustností dosahují implementace založené na využití inovativních hardwarových architektur implementovaných v FPGA případně v ASIC. Tato disertační práce popisuje nové architektury vyhledávací jednotky, které jsou vhodné pro implementaci jak v FPGA tak v ASIC. Základní myšlenkou navržených architektur je využití perfektní hashovací funkce pro implementaci přechodové tabulky konečného automatu. Dále byla navržena architektura, která umožňuje uživateli zanést malou pravděpodobnost chyby při vyhledávání a tím snížit paměťové nároky vyhledávací jednotky. Disertační práce analyzuje vliv pravděpodobnosti této chyby na celkovou spolehlivost systému a srovnává ji s řešením používaným v současnosti. V rámci disertační práce byla provedena měření vlastností regulárních výrazů používaných při analýze provozu moderních počítačových sítí. Z provedené analýzy vyplývá, že velká část regulárních výrazů je vhodná pro implementaci pomocí navržených architektur. Pro dosažení vysoké propustnosti vyhledávací jednotky práce navrhuje nový algoritmus transformace abecedy, který umožňuje, aby vyhledávací jednotka zpracovala více znaků v jednom kroku. Na rozdíl od současných metod, navržený algoritmus umožňuje konstrukci automatu zpracovávajícího libovolný počet symbolů v jednom taktu. Implementované architektury dosahují v porovnání se současnými metodami úspory paměti zlepšení až 200MB.
|
|
|
Regular Expression Based Searching in Text Files
Šimek, Ota ; Samek, Jan (referee) ; Rozman, Jaroslav (advisor)
This paper desribes the design, analysis and implementation of the program, whichis used to search for specific parts of text in text and xml files. To search, you must create a template using two text-matching technigues. These are the regular expressions and XPath expressions. This is desribed in the first chapter. Application allows to process large number of files or files with a high content.
|
|
|
Conversion of Models of Regular Languages
Navrkal, David ; Kučera, Jiří (referee) ; Křivka, Zbyněk (advisor)
p { margin-bottom: 0.08in; direction: ltr; color: rgb(0, 0, 0); line-height: 150%; widows: 2; orphans: 2; }p.western { font-family: "Times New Roman",serif; font-size: 11pt; }p.cjk { font-family: "Times New Roman",serif; font-size: 11pt; }p.ctl { font-family: "Times New Roman",serif; font-size: 12pt; } My thesis deals with how to didactically demonstrate models of regular languages focusing on their mutual conversions. These conversions are transformation of regular expressions to finite automata (FA), remove epsilon rules from FA and determinization FA. The goal was implement demonstration of these transformations in an application. In this thesis I document development of this application. This application was programmed in language C++ using graphic library Qt 5. The application was developed in an operating system (OS) Linux and tested in OS Microsoft Windows 7. All these conversions are implemented. The application is user-friendly, intuitive and functional. The application was not tested on a wider sample of students. As the main benefit, the application can help students of formal languages and finite automata better understand this theory using didactical examples. Source codes of this project (regularConvertor) are available online on Github server.
|
|
|
Dictionary Up-Translation System
Schovajsa, Michal ; Kouřil, Jan (referee) ; Smrž, Pavel (advisor)
The thesis concerns with the processing of dictionaries in electronic form, converting them into an unified form, and the problems arising in the process in particular. The subject of the work is to create a system for the elimination of some of these problems in order to facilitate machine processing of dictionaries. At first, different issues of dictionaries transferred into an unified form are concerned. Then, the thesis deals with the solution of these issues and the creation of tools for this purpose. Finally, the results and the efficiency of the instruments created are evaluated.
|
|
|
Context-Dependent Scanner
Hatina, Peter ; Koutný, Jiří (referee) ; Čermák, Martin (advisor)
This paper is devoted to principles of a lexical analysis and to a means of context resolution of a lexeme type, depending on its source code position. The lexical analysis, process of a lexical analyzer creation and possible solution for context lexeme recognition, based on a multiple automata system, is described. Lexical analyzer functionality is extended to accept tokens in other languages code blocks.
|
guest ::
