User:Richard Pinch/sandbox-4

Regular event

A set of words over a finite alphabet which can be defined by using expressions of a special form, called regular expressions. An event or language is a subset of the set $A^*$ of finite words over an alphabet $A$. The class of regular events is closed under operations of union, concatenation and iteration.

Let $L, M$ be events, that is, subsets of $A^*$. The union $L\cup M$ is the usual set-theoretic union. The concatenation $$ L \circ M = \{ \alpha \beta : \alpha \in L ,\, \beta \in M \} \ . $$ The iteration (Kleene star) $$ L^* = \{ \alpha_1 \cdots \alpha_n : n \in \mathbf{N} ,\, \alpha_i \in L \} \ . $$ We note that the empty string $\lambda$ is in $L^*$, being regarded as the concatenation of the emtpy sequence of words.

The regular events are the smallest class of events containing all singleton words $a$ for $a \in A$, and closed under union, concatenation and iteration.

We define regular expressions as algebraic expressions in the letters of $A$ with binary operators $+$ and $\cdot$, unary operator ${}^*$, and distinguished elements $\epsilon$ and $\phi$. The operators $+$ and $\cdot$ are associative, the operator $+$ is commutative and idempotent ($x+x=x$), and $\cdot$ distributes over $+$. The elements $\phi$ and $\epsilon$ are zero and unit elements. The unary ${}^*$ satisfies $$ x^* = \epsilon + x \cdot x^* = \epsilon + x^* \cdot x \ . $$

There is an order relation $\le$ on regular expressions defined by $x \le y$ if and only if $x + y = y$.

There is a relationship, "matching", between expressions and events. We say that the expression $\phi$ matches the empty event $\{ \}$, the expression $\epsilon$ matches the singleton event on the empty string $\{\lambda\}$ and that the expression $a$ matches the singleton event $\{a\}$. If expressions $\mathbf{x}$ and $\mathbf{y}$ match events $X$ and $Y$ respectively, then $\mathbf{x} + \mathbf{y}$ matches $X \cup Y$ and $\mathbf{x} \cdot \mathbf{y}$ matches $X \circ Y$; $\mathbf{x}^*$ matches $X^*$.

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
[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