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

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

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

(1) [math]\displaystyle{ \emptyset }[/math], [math]\displaystyle{ e }[/math] и [math]\displaystyle{ a }[/math] для любого [math]\displaystyle{ a\in\Sigma }[/math] --- регулярные выражения, обозначающие регулярные множества [math]\displaystyle{ \emptyset }[/math], [math]\displaystyle{ \{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) }[/math], [math]\displaystyle{ (pq) }[/math] и [math]\displaystyle{ (p)^* }[/math] --- регулярные выражения, обозначающие множества [math]\displaystyle{ P\cup Q }[/math], [math]\displaystyle{ PQ }[/math] и [math]\displaystyle{ P^* }[/math] соответственно;

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

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

Говорят, что два регулярных выражения равны (=), если они обозначают одно и то же регулярное множество.

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

Литература

[Ахо-Ульман],

[Касьянов/95]