Regular expression: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
(Отмена правки 10249 участника AlexM (обсуждение))
 
Строка 24: Строка 24:
The following property holds:
The following property holds:


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

Текущая версия от 18:59, 19 марта 2012

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))=L(w_1))\bigcup L(w_2), }[/math]

[math]\displaystyle{ L((w_1 w_2))=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].