# Regular event

A set of words over a finite alphabet which can be defined by using expressions of a special form, called regular expressions. Let $A$ be a finite alphabet and let $\cup$, $\circ$, ${}^*$ be operation symbols, called union, concatenation and iteration, respectively. Regular expressions in the alphabet $A$ are defined inductively: 1) every letter of $A$ is a regular expression; and 2) if $R_1$ and $R_2$ are regular expressions, then so are $R_1 \cup R_2$, $R_1 \circ R_2$ and $R_1^*$. The language of regular expressions is interpreted in the following way.
Let $A^*$ be the set of all words over the alphabet $A$, and let $\mathfrak{A}_1, \mathfrak{A}_2 \subseteq A^*$. The symbol of any letter of $A$ is regarded as a singleton set consisting of that letter, and $\mathfrak{A}_1 \cup \mathfrak{A}_2$ as the ordinary set-theoretical union. The set $\mathfrak{A}_1 \circ \mathfrak{A}_2$ consists of all words which are representable in the form $\alpha_1 \alpha_2$ where $\alpha_1 \in \mathfrak{A}_1$, $\alpha_2 \in \mathfrak{A}_2$; if $\mathfrak{A}_1, \mathfrak{A}_2$ contain the empty word $\lambda$, then $\alpha_1 \lambda = \alpha_1$, $\lambda \alpha_2 = \alpha_2$ and $\lambda \lambda = \lambda$. Let $\mathfrak{A} \subseteq A^*$, and for any $n \ge 2$, set $\mathfrak{A}^n = \mathfrak{A} \circ \cdots \circ \mathfrak{A}$ ($n$ times). Then $\mathfrak{A}^*$ coincides with $\mathfrak{A} \cup \mathfrak{A}^2 \cup \cdots$; that is, $\alpha \in \mathfrak{A}^*$ if and only if there is an $n \ge 1$ such that $\alpha$ is representable in the form $\alpha_1 \circ \cdots \circ \alpha_n$, where $\alpha_i \in \mathfrak{A}$ for $i = 1,\ldots,n$. Thus a set of words over a finite alphabet is a regular event if and only if it can be obtained from one-letter sets using the operations of union, concatenation and iteration a finite number of times. Regular events can also be defined using other operations that preserve regularity (for example, intersection, taking complements, etc.), and also by presenting the set of words derivable in a formal system of the type of a semi-Thue system (see Thue system), by means of grammars, etc.
A set of subsets of words over a finite alphabet $A$ (of events) together with the operations introduced on this set form a certain algebra of events. The most important of these are algebras of regular events with operations that allow all regular events to be obtained from one-letter sets. Of the greatest interest is the question of finite axiomatisability of an algebra of regular events, that is, the question of the existence in such an algebra of a finite complete system of identities. In the most general formulation, the answer to this question is negative, although there are important subalgebras of algebras of regular events in which finite complete sets of identities exist.