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.

The concept of a "regular event" arose in the study of the behaviour of finite automata (cf. Automaton, finite) regarded as acceptors. A fundamental result in the theory of finite automata is as follows: An event is representable by a finite automaton if and only if it is regular. In automata theory, two problems arose out of this: the problem of analysis: Given an automaton representing some event, to construct a regular expression defining this event; and the problem of synthesis: Given some regular expression, to construct an automaton representing the corresponding event.

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.

See also Automaton; Automata, methods of specification of; Synthesis problems.

References

[1]	V.B. Kudryavtsev, S.V. Aleshin, A.S. Podkolzin, "Elements of automata theory" , Moscow (1978) (In Russian)
[2]	A. Salomaa, "Axiomatization of an algebra of events realizable by logical networks" Probl. Kibernet. , 17 (1966) pp. 237–246 (In Russian)
[3a]	Yu.I. Yanov, "Invariant operations over events" Probl. Kibernet. , 12 (1964) pp. 253–258 (In Russian)
[3b]	Yu.I. Yanov, "Some subalgebras of events having no finite complete systems of identities" Probl. Kibernet. , 17 (1966) pp. 255–258 (In Russian)
[4]	Sh. Ushchumlich, "Investigation of some algorithms for the analysis and synthesis of automata" Soviet Math. Dokl. , 20 (1979) pp. 771–775 Dokl. Akad. Nauk SSSR , 247 : 3 (1979) pp. 561–565

Comments

Regular events are also called regular languages (cf. [a1]) and recognisable sets (cf. [a3]).

References

[a1]	A. Salomaa, "Theory of automata" , Pergamon (1969)
[a2]	J.H. Conway, "Regular algebra and finite machines" , Chapman & Hall (1971) Zbl 0231.94041 (repr. 2012) ISBN 0486485838
[a3]	S. Eilenberg, "Automata, languages and machines" , A , Acad. Press (1974)
[a4]	M.O. Rabin, O. Scott, "Finite automata and their decision problems" IBM J. Res. Devel. , 3 (1959) pp. 114–125 Zbl 0158.25404