2.2. РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ

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

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

Определение. Пусть S -конечный алфавит. Регулярное множество в (ZaewmeS определяется рекурсивно следующим образом;

(1) 0 (пустое множество) - регулярное множество в алфавите 2;

(2) [е] - регулярное множество в алфавите 2;

(3) {а} - регулярное множество в алфавите 2 для каждого a€S;

(4) если Р и Q - регулярные множества в алфавите 2, то таковы же и множества

(а) PUQ.

(б) PQ,

(в) Р*;

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

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

Определим теперь удобный способ обозначения регулярных множеств в конечном алфавите 2.

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

(1) 0 -регулярное выражение, обозначающее регулярное множество 0,

(2) е-регулярное выражение, обозначающее регулярное , множество {е\,

(3) если а $2, то а -регулярное выражение, обозначающее регулярное множество {а},

(4) если р и q - регулярные выражения, обозначающие регулярные множества Р я Q соответственно, то

(а) {p-\-q) - регулярное выражение, обозначающее P\jQ;

(б) (р{/)-регулярное выражение, обозначающее PQ;

(в) (р)*-регулярное выражение, обозначающее Р*;

(5) ничто другое не является регулярным выражением.

Мы будем пользоваться записью р+ для сокращенного обозначения выражения рр* и, кроме того, будем устранять из регулярных выражений лишние скобки там, где это не может привести к недоразумениям. В этой связи предполагается, что наивысшим приоритетом обладает операция *, затем идет конкатенация и далее операция +. Так, 0+10* означает (0-Ь(1(0*))).

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

(1) 01 обозначает {01}.

(2) О* обозначает {0}*.

(3) (0+1)* обозначает {О, 1}*.

(4) (0+1)*011 обозначает множество всех цепочек, составленных из нулей и единиц и оканчивающихся цепочкой 011.

(5) (а + Ь) (а + Ь + 0+1)* обозначает множество всех цепочек нз {О, 1, а, Ь}*, начинающихся с а или Ь.

(6) (00 + 11)*((01 + 10)(00+11)*(01 + 10)(00+11)*)* обозначает множество всех цепочек нулей и единиц, содержащих четное число нулей и четное число единиц. □

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

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

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

Лемма 2.1. Пусть а, р w у -регулярные выражения. Тогда (I) а + р-р + а (2) 0*- е

(3) a+(p + Y)-(a + p) + ? (4) а(р7)(ар)7

(5) а(Р + 7)--ар + аТ (6) (а + Р)т = «Т + РТ

(7) ае = еа = а (8) 0аа0 = 0

(9) а*а + а* (10) (а*)*=(х*

(U) аа==а (12) а + 0=а

Доказательство. (1) Пусть а и 3 обозначают множества Li и соответственно. Тогда (х + Р обозначает LuL, а р + а обозначает Но LiiLLijLj по определению объеди-

нения. Следовательно, а + р = р + сх.

Доказательство остальных равенств оставляем в качестве упражнения. □

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

При работе с языками часто бывает удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества. Мы рассмотрим здесь системы уравнений, коэффициенты которых - регулярные выражения. Такие уравнения будем Называть уравнениями с регулярными коэффициентами.

Рассмотрим, например, уравнение с регулярными коэффициентами

(2.2.1)

Х = аХЬ

где а и b - регулярные выражения. Легко проверить прямой подстановкой, что Х=:а*Ь - решение уравнения (2.2.1). Иначе говоря, если в обе части уравнения (2.2.1) подставить а*Ь вместо X, то слева и справа будет одно и то же множество.

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

.о 9 m ХаХ + а,Г + а,

y = b,X + b,V + b,

где и для всех / = 1, 2, 3 являются регулярными выражениями. Покажем, как решить эту систему уравнений и получить решение

X = (й! + ablb) («3 + ablb)

Однако сначала отметим, что не все уравнения с регулярными коэффициентами обладают единственным решением. Например, если

(2.2.3)

Х-аХ + р

- уравнение с регулярными коэффициентами и а обозначает множество, содержащее пустую цепочку, то Х = а*фу) будет решением уравнения (2.2.3) для любого у [у не обязано даже быть регулярным, см. упр. 2.2.7). Таким обра.зом, уравнение (2.2.3) имеет бесконечно много решений. В такого рода ситуациях мы будем брать наименьшее решение, которое назовем

где все a,-j - регулярные выражения в алфавите, не пересекающемся с Д.

Коэффициентами уравнений являются выражения aj. Заметим, что если а-у = 0 (такое регулярное выражение возможно), то в уравнении для Х нет члена, содержащего Ху. Аналогично, если ct,y = e, то в уравнении для X,- член, содержащий Ху,- это просто Ху. Иными словами, 0 играет роль коэффициента О, а е - роль коэффициента 1 в обычных линейных уравнениях.

Алгоритм 2.1. Решение стандартной системы уравнений с регулярными коэффициентами.

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите 2 и с множеством неизвестных

А = {1.....X,.}-

Выход. Решение системы Q в виде Xj = a, Х„а„, где а- - регулярное выражение в алфавите 2.

Метод. Метод напоминает решение системы линейных уравнений методом исключения Гаусса.

Шаг 1. Положить /=1.

Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы 2.1 записать уравнение для X,- в виде X,-аХ/ + р, где а-регулярное выражение в алфавите 2, а р-регулярное выражение вида po + p,XfH.i-j-...+р„Х„, причем все р;-регулярные выражения в алфавите 2. (Мы увидим, что это всегда возможно.) Затем в правых частях уравнений для Х,-+1, Х„ заменить X,- регулярным выражением а*р.

Шаг 3. Увеличить t на 1 и вернуться к шагу 2.

Шаг 4. Записать уравнение для Х„ в виде X„ = aX„-f р, где а и р -регулярные выражения в алфавите 2. (После выполнения шага 2 для каждого i < п в правой части уравнения для

X,- не будет неизвестных X,.....I-i- В частности, на шаге 4

этим свойством будет обладать и уравнение для Х„.) Перейти к шагу 5 (при этом / -п).

Шаг 5. Уравнение для Х- имеет вид X,- аХ,Ч-р> где а и Р - регулярные выражения в алфавиЬе. Записать на выходе

наименьшей неподвижной точкой. Наименьшая неподвижная точка уравнения (2.2.3)-это множество Л" = а*р.

Определение. Систему уравнений с регулярными коэффициентами назовем стандартной системой с множеством неизвестных Х, Л",,}, если она имеет вид

Х--а*р и в уравнения для ---уХ подставить а*р вместо Х.

Шаг 6. Если остановиться. В противном случае уменьшить г на 1 и вернуться к шагу 5. □

Пример 2.9, Пусть A--{Xi, Х, Х}. Рассмотрим систему уравнений

(2.2.4) Xi-OX, + lXi + e

(2.2.5) Х,ОХ,\Х,

(2.2.6) X, = OXi\X,

Из уравнения (2.2.4) получаем lXj + (0X2 + e). Затем в

остальные уравнения подставляем 1*(0Л2Н-е) вместо Х. Уравнение (2.2.6) принимает вид

Х,---0\ЦОХ, + е)+\Х,

или с учетом леммы 2.1

(2.2.7) Хз-01*0Х,+ 1Хз + 01*

Если теперь из уравнения (2.2.5), которое мы еще не трогали, выразить Ха через Хд и в (2.2.7) подставить 1*0Хз вместо Х, то получим

(2.2.8) Хз = (01*01*0+1)Хз + 01*

Теперь в алгоритме 2.1 мы дошли до шага 5. Из уравнения

(2.2.8) находим решение для Х:

(2.2.9) Хз = (01*01*0+1)*01* Подстановка (2.2.9) в (2.2.5) дает

(2.2.10) Х, = 0(01*01*0+1)*01*+1Х2

Так как Х3 не входит в уравнение (2.2.4), то оно не меняется. Затем решаем (2.2.10) и получаем

(2.2.11) Х2= 1*0(01*01*0+1)*01*

Подставляем (2.2.11) в (2.2.4):

(2.2.12) Xi = 0l*0(01*01*0+l)*01* + lXi + e

Решением уравнения (2.2.12) будет

(2.2.13) Xi = l*(01*0(0l*0l*0+l)*01* + e)

Выход алгоритма 2.1 -равенства (2.2.9), (2.2.11) и (2.2.13). □

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

нении обе его части будут обозначать одно и то же множество. Как уже указывалось, решение стандартной системы уравнений не всегда единственно. Однако мы увидим, что в таком случае алгоритм 2.1 дает наименьшую неподвижную точку.

Определение. Пусть Q-стандартная система уравнений с множеством неизвестных Дне коэффициентами в алфавите 2. Отображение f множества Д в множество языков в алфавите 2 называют решением системы Q, если после подстановки в каждое уравнение /(X) вместо X для каждого ХД уравнения становятся равенствами множеств. Отображение /: А-5(2*) называют наименьшей неподвижной точкой системы Q, если / - решение и для любого другого решения g

f{X)g{X) для всех Х€Д

Следующие две леммы содержат полезную информацию о наименьших неподвижных точках.

Лемма 2.2. Каждая стандартная система уравнений Q с неизвестными Д обладает единственной наименьшей неподвижной точкой.

Доказательство. Пусть f (X) {w\wg (X) для всех решений g системы Q} для всех ХД. Можно прямо показать, что / - решение и f{X)g{X) для всех решений g. Таким образом, / - единственная наименьшая неподвижная точка системы Q. □

Теперь дадим некоторую характеристику наименьшей неподвижной точки.

Лемма 2.3. Пусть Q-стандартная система уравнений с неизвестными A = {Xj, Х„} и уравнение для X,- имеет вид

Xi = а,-, + а,.Х + азХ, + .. . + а,.„Х„

Тогда наименьшей неподвижной точкой системы Q будет такое отображение /, что f{Xj-) - {Wi ... w\waf о и wjcc для некоторой последовательности чисел п, где ml,

\km и Ji = i}.

Доказательство. Легко проверить непосредственно, что для всех /

f(X,.)-a,,UaJ (-:jU...Ua,J(X„)

Таким образом, / - решение.

Чтобы показать, что / - наименьшая неподвижная точка, предположим, что g-решение и для некоторого / существует цепочка wf (Xi)~g(Х). Так как шf (X,-), то можно записать

А. Ахо, Дж, Ульман, т. 1 129