Регулярные выражения

Регулярные выражения (Regular expressions) — метод задания регулярных множеств.

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

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

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

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

Обычно используется запись [math]\displaystyle{ \,p^+ }[/math] для сокращенного обозначения выражения [math]\displaystyle{ \,pp^* }[/math] и, кроме того, устраняются из регулярных выражений лишние скобки там, где это не может привести к недоразумениям. (Предполагается, что наивысшим приоритетом обладает операция [math]\displaystyle{ \,^* }[/math], затем идет конкатенация и далее операция [math]\displaystyle{ \,+ }[/math].)

Говорят, что два регулярных выражения равны ([math]\displaystyle{ \,= }[/math]), если они обозначают одно и то же регулярное множество.

Используется и другие методы задания языков, каждый из которых определяет в точности регулярные множества. Среди них — автоматные грамматики, праволинейные грамматики, регулярные грамматики, конечные автоматы, детерминированные конечные автоматы.

Литература

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

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