Regular expression

Regular expression --- регулярное выражение.

Assume that [math]\displaystyle{ \Sigma }[/math] and [math]\displaystyle{ \Sigma'=\{+, ^*, \emptyset , (,)\} }[/math] are disjoint alphabets. A string [math]\displaystyle{ w }[/math] over the alphabet [math]\displaystyle{ \Sigma \bigcup \Sigma' }[/math] is a regular expression over [math]\displaystyle{ \Sigma }[/math] iff [math]\displaystyle{ w }[/math] is a symbol of [math]\displaystyle{ \Sigma }[/math], or the symbol [math]\displaystyle{ \emptyset }[/math], or [math]\displaystyle{ w }[/math] is of one of the forms [math]\displaystyle{ (w_1 +w_2) }[/math], [math]\displaystyle{ (w_1 w_2) }[/math], [math]\displaystyle{ (w_1)^* }[/math], where [math]\displaystyle{ w_1 }[/math] and [math]\displaystyle{ w_2 }[/math] are regular expressions over [math]\displaystyle{ \Sigma }[/math].

Each regular expression [math]\displaystyle{ w }[/math] over [math]\displaystyle{ \Sigma }[/math] denotes a language [math]\displaystyle{ L(w) }[/math] over [math]\displaystyle{ \Sigma }[/math] according to following conventions:

(1) the language denoted by [math]\displaystyle{ \emptyset }[/math] is the empty set,

(2) the language denoted by [math]\displaystyle{ a \in \Sigma }[/math] consists of the string [math]\displaystyle{ a }[/math],

(3) for all regular expressions [math]\displaystyle{ w_1 }[/math] and [math]\displaystyle{ w_2 }[/math] over [math]\displaystyle{ \Sigma }[/math], we have

[math]\displaystyle{ L((w_1 +w_2)) }[/math]=[math]\displaystyle{ L(w_1))\bigcup L(w_2), }[/math]

[math]\displaystyle{ L((w_1 w_2)) }[/math]=[math]\displaystyle{ L(w_1)L(w_2), }[/math]

[math]\displaystyle{ L((w)^*) }[/math]=[math]\displaystyle{ (L(w))^* }[/math].

The following property holds:

[math]\displaystyle{ L }[/math]=[math]\displaystyle{ L(w) }[/math] for a regular expression [math]\displaystyle{ w }[/math] over [math]\displaystyle{ \Sigma }[/math] iff [math]\displaystyle{ L }[/math] is a \emph{regular language} over [math]\displaystyle{ \Sigma }[/math].