Part 2. Special Issues in Intellectual Systems Theory

Finite automaton modification by using compression algorithms

A. Bernadotte

Lomonosov Moscow State University

Abstract: The question of whether a word belongs to a given regular language finds its application in areas where it is relevant to search for certain patterns in data of different nature. Growth of the deterministic finite automaton (DFA) states number which is exponential in number of regular expressions of the given language is still a real problem. In this article, we take a look at modifying a finite automaton by using compression algorithms. These approaches modify the finite automaton without changing the language and without adding additional structural elements.

Keywords: DFA, NDF, regular language, exponential blowup, compression algorithm.