|
Reduction of the Nondeterministic Finite Automata
Procházka, Lukáš ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.
|
| |
| |
|
Languages, Grammars and Machines
Mocková, Ľubica ; Zimmerová, Barbora (referee) ; Bobalová, Martina (advisor)
My thesis is a brief synopsis of the basic types of formal languages, grammars and machines, which are a part of theoretical computer science. My thesis contains the survey of the theory related to the given topic and problems related to the theoretical part of my thesis. This work is to be used as a study material for the students of the Faculty of Business and Management for the subject of Discrete Mathematics. It can also be helpful for the students of other universities and faculties whose curricula contain theory of grammars and machines.
|
|
Automatic Grouping of Regular Expressions
Stanek, Timotej ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This project is about security of computer networks using Intrusion Detection Systems. IDS contain rules for detection expressed with regular expressions, which are for detection represented by finite-state automata. The complexity of this detection with non-deterministic and deterministic finite-state automata is explained. This complexity can be reduced with help of regular expressions grouping. Grouping algorithm and approaches for speedup and improvement are introduced. One of the approches is Genetic algorithm, which can work real-time. Finally Random search algorithm for grouping of regular expressions is presented. Experiment results with these approches are shown and compared between each other.
|
| |
| |
|
Languages, Grammars and Machines
Mocková, Ľubica ; Zimmerová, Barbora (referee) ; Bobalová, Martina (advisor)
My thesis is a brief synopsis of the basic types of formal languages, grammars and machines, which are a part of theoretical computer science. My thesis contains the survey of the theory related to the given topic and problems related to the theoretical part of my thesis. This work is to be used as a study material for the students of the Faculty of Business and Management for the subject of Discrete Mathematics. It can also be helpful for the students of other universities and faculties whose curricula contain theory of grammars and machines.
|
|
Reduction of the Nondeterministic Finite Automata
Procházka, Lukáš ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.
|
|
Automatic Grouping of Regular Expressions
Stanek, Timotej ; Kořenek, Jan (referee) ; Kaštil, Jan (advisor)
This project is about security of computer networks using Intrusion Detection Systems. IDS contain rules for detection expressed with regular expressions, which are for detection represented by finite-state automata. The complexity of this detection with non-deterministic and deterministic finite-state automata is explained. This complexity can be reduced with help of regular expressions grouping. Grouping algorithm and approaches for speedup and improvement are introduced. One of the approches is Genetic algorithm, which can work real-time. Finally Random search algorithm for grouping of regular expressions is presented. Experiment results with these approches are shown and compared between each other.
|