Namespaces
Variants
Actions

Difference between revisions of "Regular event"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (→‎References: expand bibliodata)
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
A set of words over a finite alphabet which can be defined by using expressions of a special form, called regular expressions. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807001.png" /> be a finite alphabet and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807002.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807003.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807004.png" /> be operation symbols, called union, concatenation and iteration, respectively. Regular expressions in the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807005.png" /> are defined inductively: 1) every letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807006.png" /> is a regular expression; and 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807007.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807008.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r0807009.png" /> are regular expressions, then so are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070012.png" />. The language of regular expressions is interpreted in the following way.
+
A set of [[word]]s 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070013.png" /> be the set of all words over the alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070014.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070016.png" />. The symbol of any letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070017.png" /> is regarded as a set consisting of one letter, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070018.png" /> as the ordinary set-theoretical union. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070019.png" /> consists of all words which are representable in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070020.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070022.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070024.png" /> contain the empty word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070025.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070028.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070029.png" />, and for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070030.png" />, set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070031.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070032.png" /> times). Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070033.png" /> coincides with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070034.png" />; that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070035.png" /> if and only if there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070036.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070037.png" /> is representable in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070038.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070039.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070040.png" />. 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|Thue system]]), by means of grammars, etc.
+
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|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.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r080/r080700/r08070041.png" /> (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 axiomatizability 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.
+
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|Automaton]]; [[Automata, methods of specification of|Automata, methods of specification of]]; [[Synthesis problems|Synthesis problems]].
+
See also [[Automaton]]; [[Automata, methods of specification of]]; [[Synthesis problems]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  V.B. Kudryavtsev,  S.V. Aleshin,  A.S. Podkolzin,  "Elements of automata theory" , Moscow  (1978)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A. Salomaa,  "Axiomatization of an algebra of events realizable by logical networks"  ''Probl. Kibernet.'' , '''17'''  (1966)  pp. 237–246  (In Russian)</TD></TR><TR><TD valign="top">[3a]</TD> <TD valign="top">  Yu.I. Yanov,  "Invariant operations over events"  ''Probl. Kibernet.'' , '''12'''  (1964)  pp. 253–258  (In Russian)</TD></TR><TR><TD valign="top">[3b]</TD> <TD valign="top">  Yu.I. Yanov,  "Some subalgebras of events having no finite complete systems of identities"  ''Probl. Kibernet.'' , '''17'''  (1966)  pp. 255–258  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  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</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  V.B. Kudryavtsev,  S.V. Aleshin,  A.S. Podkolzin,  "Elements of automata theory" , Moscow  (1978)  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  A. Salomaa,  "Axiomatization of an algebra of events realizable by logical networks"  ''Probl. Kibernet.'' , '''17'''  (1966)  pp. 237–246  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[3a]</TD> <TD valign="top">  Yu.I. Yanov,  "Invariant operations over events"  ''Probl. Kibernet.'' , '''12'''  (1964)  pp. 253–258  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[3b]</TD> <TD valign="top">  Yu.I. Yanov,  "Some subalgebras of events having no finite complete systems of identities"  ''Probl. Kibernet.'' , '''17'''  (1966)  pp. 255–258  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top">  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</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
Regular events are also called recognizable sets (cf. [[#References|[a3]]]).
+
Regular events are also called regular languages (cf. [[#References|[a1]]]) and recognisable sets (cf. [[#References|[a3]]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Salomaa,  "Theory of automata" , Pergamon  (1969)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Conway,  "Regular algebra and finite machines" , Chapman &amp; Hall  (1971)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , '''A''' , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M.O. Robin,  O. Scott,  "Finite automata and their decision problems"  ''IBM J. Res. Devel.'' , '''3'''  (1959)  pp. 114–125</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Salomaa,  "Theory of automata" , Pergamon  (1969)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  J.H. Conway,  "Regular algebra and finite machines" , Chapman &amp; Hall  (1971) {{ZBL|0231.94041}} (repr. 2012) ISBN 0486485838</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , '''A''' , Acad. Press  (1974)</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  M.O. Rabin,  O. Scott,  "Finite automata and their decision problems"  ''IBM J. Res. Devel.'' , '''3'''  (1959)  pp. 114–125 {{ZBL|0158.25404}}</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Revision as of 17:06, 2 April 2016

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
How to Cite This Entry:
Regular event. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Regular_event&oldid=15972
This article was adapted from an original article by V.A. Buevich (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article