Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 26
Текст из файла (страница 26)
К сожалению, для каждого регулярного множества существует бесконечно много обозначающих его регулярных выражений. Будем говорить, что два регулярных выражения равны (=), если они обозначают одно и то же множество. В следующей лемме устанавливаются некоторые Основные алгебраические свойства регулярных выражений. Лемма 2.1. Пусть а, (1 и Т вЂ” регулярные выражения.
Тогда (1) -)-6 = й -(- (2) 4д'*=- е (3) и+(()+Т)=(а+)))+Т (4) а(()Т) — (ир) у (6) иФ+Т)= Р+ у (6) (а+6) Т=ау+ру (7) ае=еа =се (8) йэа==айз =1у (9) а*=а+а~ (10) (а")*=а* (11) а+а=сг (12) а + )Ь' = се ГЛ. З. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Доказательство. (1) Пусть а и (з обозначают множества Ц и Г., соответственно. Тогда а+р обозначает 7., Вй„а ()+а обозначает Т.,(!с', Но Е.с(!с,=1.,!!Т,с по определению объединения. Следовательно, сх+ (1 р+ сх.
Доказательство остальных равенств оставляем в качестве упражнения, [] В дальнейшем мы не будем различать регулярное выражение и обозначаемое им множество, если это не приводит к недоразумениям. Например, в силу этого соглашения символ а будет представлять множество (а). При работе с языками часто бывает удобно пользоваться уравнениями, коэффициентами и неизвестными которых служат множества.
Мы рассмотрим здесь системы уравнений, коэффициенты которых — регулярные выражения. Такие уравнения будем называть уравнениями с регулярными коэффицссенталси. Рассмотрим, например, уравнение с регулярными коэффициентами (2.2.1) Х=аХ+Ь где а и Ь вЂ” регулярные выражения, Легко проверить прямой подстановкой, что Х= а'Ь вЂ” решение уравнения (2.2.1). Иначе говоря, если в обе части уравнения (2.2.1) подставить а'Ь вместо Х, то слева и справа будет одно и то же множество. Можно рассматривать также системы уравнений, определяющие языки. Возьмем, например, пару уравнений Х вЂ” - асХ+ а,)'+с', )с =.. Ь,Х + Ь, 1'+ Ь, где а, и Ь, для всех с' — 1, 2, 3 являются регулярными выражениями.
Покажем, как репсить эту систему уравнений и получить решение Х =- (а, + а,Ь,"Ь,)'(а, + а,Ь,*Ь,) Однако сначала отметим, что не все уравнения с регулярными коэффициентами обладают единственным решением. Например, если (2.2.3) Х =:= аХ+ )3 — уравнение с регулярными коэффициентами и гс обозначает множество, содержащее пустую цепочку, то Х=а'ф+у) будет решением уравнения (2.2.3) для любого у (у не обязано даже быть регулярным, см. упр. 2.2,7). Таким образом, уравнение (2.2.3) имеет бесконечно много решений. В такого рода ситуациях мы будем брать наименьшее решение, которое назовем Э.З.
РЕГУЛЯРНЫЕ МНОЖЕСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИР наименьшей неподвижной точкой. Наименьшая неподвижная точка у-равнения (2.2.3) — это множество Х = а*5. Определение. Систему уравнений с регулярными коэффициентами назовем етандартнай системой с множеством неизвестных А = (Хс, Х„, ..., Х„), если она имеет вид Хс=-асс+ассХс-(-а„Хс+... +М,„Х„ где все яы — регулярные выражения в алфавите, не пересекаю. щемся с А. Коэффициентами уравнений являются выражения ас Заметим, что если ас, — Я (такое регулярное выражснне возможно), то в уравнении для Хс пет члена, содержащего Х;.
Аналогично„ если аы — — е, то в уравнении для Х; член, содержащий Х,,— это просто Х . Иными словами, Я играет роль коэффициента О„а е — роль коэффициента 1 в Обычных линейных уравнениях. Алгоритм 2.!. Решение стандартной системы уравнений с регулярными коэффициентами. Вход. Стандартная система !г уравнений с регулярными коэффициентами в алфавите г'.
и с множеством нсизвестных А=-(Х„..., Х,,). Вьсхад, Решение системы (г в виде Х =а„..., Х„=-а„, где ас — регулярное выражение в алфавите Метод. Метод напоминает решение системы линейных уравнений методом исключения Гаусса. Шаг 1. Положить с — 1. Шаг 2. Если с'=и, перейти к шагу 4. В противном случае с помощью тождеств леммы 2.1 записать уравнение для Хс в виде Х, =аХГ-1-!1, где гс — регулярное выражение в алфавите л, а р — регулярное выражение вида 5,+!з,Х,„,-(-... +5„Хси причем все (1с — регулярные выражения в алфавите г. (Мы увидим, что это всегда возможно.) Затем в правых частях уравнений для Хс+„..., Х„заменить Х; регулярным выражением а*ф.
Шаг 3. Увеличить с' на 1 и вернуться к шагу 2. Шаг 4. Записать уравнение для Х„в виде Х„=аХ„+5, где а и р — регулярные выражения в алфавите г'. (После выполнения шага 2 для каждого с'(и в правой части уравнения для Х; не будет неизвестных Х„..., Хс,. В частности, на шаге 4 этим свойством будет обладать н уравнение для Х„,) Псрсйтн к спагу 5 (прп этом с'=-и).
Шаг 5. Уравнение для Х, имеет в Х;=аХсц (1, где сс и (с — регулярные выражения н алфави . Записать на выходе 127 Гл, 2. элементы теОРии языкОВ 2.2. РЕГУЛЯРг!ЫЕ МНОЖРСТВА, ИХ РАСПОЗНАВАНИЕ И ПОРОЖДЕНИЕ Х,=а*)3 и в уравнения для Хг „..., Х, подставить гх*!) вместо Хг.
Шаг 6. Если !'=-1, остановиться. В противном случае умень- шить г на 1 и вернуться к шагу 5. Г') Пример 2.9, Пусть Л =- (Х„Х„Х2). Рассмотрим систему уравнений (2.2.4) Х, =ОХ, + 1Х2+в (2.2.5) Х,=:ОХ,+1Х, (2.2.6) Х,=-ОХ,+1Х, Из уравнения (2.2.4) получаем Х, = 1Хг+(ОХ, +е). Затем в остальные уравнения подставляем 1*(ОХ,+е) вместо Хгл Урав- нение (2.2.6) принимает вид Х,.-.—. 01* (ОХ, + в) + 1Х, нли с учетом леммы 2.! (2.2.7) Х, = 01*ОХ, + 1 Х„+ 01' Если теперь из уравнения (2.2.5), которое мы еще не тро- гали, выразить Х, через Х, и в (2,2.7) подставить 1'ОХ, вместо Х„то получим (2.2.8) Х,=(01 01 О+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) Х,=О(01*01'О+!)"01'+1Х, Так как Х, не входит в уравнение (2,2.4), то оно не меняется. Затем решаем (2.2.10) и получаем (2.2.11) Х, = 1 0(01*0 1*0 + 1)*01 Подставляем (2.2.11) в (2.2.4): (2.2.! 2) Х, = 01*0(01'01'0+ 1)'01'+1Х, + е Решением уравнения (2.2.12) будет (2,2.13) Х, = 1'(О!'0(0! "0!'О+ 1)*01'+ в) Выход алгоритма 2.1 — равенства (2.2.9), (2.2.11) и (2.2.13). С) Мы должны показать, что выход алгоритма 2.1 действительно является решением данной систсмы уравнений в том смысле, что если подставить решение вместо неизвестных, то в каждом урав228 ненни обе его части будут обозначать одно и то же множество. Как уже указывалось, решение стандартной системы уравнений не всегда единственно.
Однако мы увидим, что в таком случае алгоритм 2,1 дает наименьшую неподвижную точку. Определение. Пусть ге †стандартн система уравнений с множеством неизвестных Л и с козффициентами в алфавите 2'. Отображение )' множества Л в множество языков в алфавите л называют решением системы г,г, если после подстановки в каждое уравнение )(Х) вместо Х для каждого ХЕЛ уравнения становятся равенствами множеств. Отображение 7: Л вЂ” Р(2') называют наименьшей неподвижной точкой системы (г, если 7'— решение и для любого другого решения я 7 (Х) с= а(Х) для всех Х Е Л Следующие две леммы содержат полезную информацию о наименьших неподвижных точках.
Лемма 2.2. Каждая стандартная сиапема уравнений гг с неизвестными Л обладает единственной наименьшеи неподвижной точкой. Доказательство. Пусть 1(Х).=-(и!~и!Ей(Х) для всех решений я системы (г) для всех Хе Л. Можно прямо показать, что 7 — решение и 7(Х) ы я(Х) для всех решений д, Таким образом, 7 †единственн наименьшая неподвижная точка системы гг. () Теперь дадим некоторую характеристику наименьшей неподВижной точки.
Лемма 2.3. 11усть Π— стандартная система уравнений с неизвестнылш Л =(Х„..., Х„) и уравнение для Х, имеет вид Х; = аг, + аггХ2+ аггХ2+... + гхг„Х„ Тогда наименьшей неподвижной точкой системы Я будет такое отображение !", что ! (Х!) =(иг, ... Нг,„!иг„,Еггг„о и игАЕсгг„! для некоторой последсвательноепги чисел 12, ..., 1„, где пг=-: 1, 1(й~т и 1,— г). Доказательство. Легко проверить непосредственно, что для всех г' ~ (Хг) = гзм !г а;,~ (Х,) !г... !г гхг„~ (Х„) Таким Образом, 7' — решение. Чтобы показать, что 7 — панменьшая неподвижная точка, предположим, что д — решение и для некоторого г существует цепочка игЕ~(Хг) — д(Х!). Так как и!ч!" (Х,), то можно записать А, Аль, Дгл. Уллили, 2.
1 ГЛ. !. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ 2.2. РегкляРные мнОжестВА, их РАспознАВАние ипОРОждение (Заметны, что для 1(й < ! коэффициент при Ав равен 8.) В системах ()! и 1'„|, уравнения для Л„при й«:!' совпадают. Допустим, что Ау — — а,,+ ~ а|ААА А=! (2.2.14) — уравнение для А, в системе |г, при 1' ~ П В системе Я, уравнением для Л будет (2.2.15) А,=й,+ 2~ рААА А=|в! где р, = а + а;аиа!~ рь=а.ь+ау|ата|1 для ! (Й" и С помощью леммы 2.3 можно получить представления для наименьших неподвижных точек систем (г, и |г„которые мы обозначим соответственно через 1! и 1,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
