Pseudo-automata for generalized regular expressions

Abstract

In this paper, we introduce a new formalism which is intended for representing a special extensions of finite automata. We call them generalized nondeterministic finite pseudo-automata. This formalism gives not only the equivalence between two classes of finite automata, i.e., ordinary nondeterministic finite automata and pseudo-automata introduced by us, which also define all the regular languages. This formalism also gives an opportunity of defining the complement operation (and, therefore, generalized regular expressions) in a way similar to the usual “automata” methods. We use the term “pseudo-automata”, because, unlike usual automata constructions (ordinary nondeterministic finite automata, push-down automata, Turing machines etc.), we do not indicate the concrete paths for defining the considered word of the given regular language; the introduced formalism gives only the algorithm for answering the question, whether the given word belongs to the considered language. In the paper, we firstly give definition of the pseudo-automata and their languages. After that, we consider the diagrams allowing to visualize them and give some examples. Then we consider some properties of introduced formalism.