Регулярные множества и выражения

Введем понятие регулярного множества, играющего важную роль в теории формальных языков.

Регулярное множество в алфавите T определяется рекурсивно следующим образом:

• 
  (пустое множество) - регулярное множество в алфавите T;
• {e} - регулярное множество в алфавите T (e - пустая цепочка);
• {a} - регулярное множество в алфавите

  T для каждого a

  
  T;
• если P и Q - регулярные множества в алфавите T, то регулярными являются и множества

• P
  
  Q (объединение),
• PQ (конкатенация, т.е. множество {pq|p
  
  P, q
  
  Q}),
• P* (итерация: P* =
  

  n=0

  
  Pn);

ничто другое не является регулярным множеством в алфавите T.

Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо

, либо {e}, либо {a} для некоторого a T, либо его

можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

Приведенное выше определение регулярного множества позволяет ввести следующую удобную форму его записи, называемую регулярным выражением.

Регулярное выражение в алфавите T и обозначаемое им регулярное множество в алфавите T определяются рекурсивно следующим образом:

• 
  - регулярное выражение, обозначающее множество 
  
  ;
• e - регулярное выражение, обозначающее

  множество {e};

• a - регулярное выражение, обозначающее множество {a};
• если p и q - регулярные выражения, обозначающие регулярные множества P и Q соответственно, то

• (p|q) - регулярное выражение, обозначающее регулярное множество P
  
  Q,
• (pq) - регулярное выражение, обозначающее регулярное множество PQ,
• (p*) - регулярное выражение, обозначающее регулярное множество P*;

ничто другое не является регулярным

выражением в алфавите T.

Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет.

Кроме того, мы будем пользоваться записью p+ для обозначения pp*. Таким образом, запись (a|((ba)(a*))) эквивалентна a|ba+.

Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением

r.

Пример 3.1. Несколько примеров регулярных выражений и обозначаемых ими регулярных множеств:

• a(e|a)|b - обозначает множество {a, b, aa};



• a(a|b)* - обозначает множество всевозможных цепочек, состоящих из a и b, начинающихся с a;



• (a|b)*(a|b)(a|b)* - обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество {a, b}+;



• ((0|1)(0|1)(0|1))* - обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3.

Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это

множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений.

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

Существует ряд алгебраических законов, позволяющих осуществлять эквивалентное преобразование регулярных выражений.

Лемма. Пусть p, q и r - регулярные выражения. Тогда справедливы следующие соотношения:

	(1)	p|q = q|p;			(7)	pe = ep = p;
	(2)	* = e;			(8)	p = p = ;
	(3)	p|(q|r) = (p|q)|r;			(9)	p* = p|p*;
	(4)	p(qr) = (pq)r;			(10)	(p*)* = p*;
	(5)	p(q|r) = pq|pr;			(11)	p|p = p;
	(6)	(p|q)r = pr|qr;			(12)	p| = p.

Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть , либо не содержит в своей записи .

В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи .

При практическом описании лексических структур бывает полезно сопоставлять регулярным выражениям некоторые имена, и ссылаться на них по этим именам. Для

определения таких имен мы будем использовать запись вида

	d1 = r1
	d2 = r2
	...
	dn = rn

где di - различные имена, а каждое ri - регулярное выражение над символами T{d1, d2, ..., di-1}, т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого ri можно построить регулярное выражение над T, повторно заменяя имена регулярных выражений на обозначаемые ими регулярные выражения.



Пример 3.2. Использование имен для регулярных выражений.

• Регулярное выражение для множества идентификаторов.
  
  

  	Letter = a|b|c|...|x|y|z
  	Digit = 0|1|...|9
  	Identifier = Letter(Letter|Digit)*

• Регулярное выражение для множества чисел в десятичной записи.
  
  

  	Digit = 0|1|...|9
  	Integer = Digit+
  	Fraction = .Integer|e
  	Exponent = (E(+|-|e)Integer)|e
  	Number = Integer Fraction Exponent

Содержание раздела

---

---