Регулярные выражения: различия между версиями

'''Регулярные выражения''' ([[Regular expressions]]) —

'''Регулярные выражения''' в некотором алфавите <math>\,\Sigma</math> и регулярные множества, которые они ''обозначают'', определяются рекурсивно следующим образом:

:(1) <math>\emptyset,\,e</math> и <math>\,a</math> для любого <math>a\in\Sigma</math> — регулярные выражения, обозначающие регулярные множества <math>\emptyset,\,\{e\}</math> и <math>\,\{a\}</math>;

:(2) если <math>\,p</math> и <math>\,q</math> — регулярные выражения, обозначающие регулярные множества <math>\,P</math> и <math>\,Q</math> соответственно, то <math>\,(p+q),\,(pq)</math> и <math>\,(p)^*</math> — регулярные выражения, обозначающие множества <math>P\cup Q,\,PQ</math> и <math>\,P^*</math> соответственно;

:(3) других регулярных выражений нет.

Обычно используется запись <math>\,p^+</math> для сокращенного обозначения

выражения <math>\,pp^*</math> и, кроме того, устраняются из регулярных выражений

(Предполагается, что наивысшим приоритетом обладает операция <math>\,^*</math>,

затем идет конкатенация и далее операция <math>\,+</math>.)

Говорят, что два регулярных выражения ''равны'' (<math>\,=</math>), если они

точности регулярные множества. Среди них —

* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.