Generalized indeterministic finite automata

The article considers the formalism used for representing a special class of extensions of finite automata, so-called generalized indeterministic finite automata. The described algorithms of equivalent transformations of such automata and also their analogue of Kleene theorem result in not only the equivalence between such and usual finite automata (such equivalence is obvious a priori), but also in the possibility of defining the complement operation (and, generally, the generalized regular expressions) by usual “automata” methods. The work also describes the construction method of the specific generalized automaton, which determines the given generalized regular expression. The given method results from the Kleene theorem analogue proving. Extended opportunities for regular languages description introduced in the article may be of use in several applications, e.g. in contextual search.