Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 51
Текст из файла (страница 51)
Проверка достоверности этих аксиом требует рассмотрения совершенно общих случаев. Поэтому их трудно должным образом описать. Тем не менее, чтобы обозначить используемые ниже идеи, рассмотрим два примера, исходя из двух аксиом, примененных к конкретному регулярному выражевию.
Пример ЗЛ. Пусть А (аЬ": Оа и). Это выражение регулярно, так как является представимым для машины М, нзображенной на рис. 9,17,а. Рве. 9Л7 Используя машину, изображенную на рис. 9.16,а, которая распознает О, и применяя подходящее построение, получим машину, изображенную на рнс. 9.17,Ь, которая, очевидно, эквивалентна М. Следовательно, А А+О. е' Пример 8.2. Используя А и 1, определяемые машинами, данными выше, и обычной конструкцией конкатенации, получаем недетерминированпый конечный распознаватель, иаображенпый на рис. 9.18,а, который будет представлять строки в регулярном выражении 1А. Эту машину делаем детерминированной (рис. 9.18,Ь), затем получаем машину (рис.
9.18,е), эквивалентную М, которая удовлетворяет (в данном случае) части аксиомы 6), а именно 1А А. е Определив регулярную алгебру, посмотрим, как ее использовать. Предположим, что А, В и С являются заданными регулярными выражеипямя (мпожсстиами строк) 333 и что Х и У вЂ” неизвестные регулярные выражения такие, что выполпевы следу1ощие соотвошевия: Х АХ+ ВУ, У ХС+ В. Существуют ли решения этих «уравиевий», и если да, то как их пайгин Как мы вскоре уввдим, регулярные Рвс. 9Л8 уравнения ве имеют единственного решения; поэтому мы ввачале введем попятив аппроксимации для регулярных выражений. Определение. Для регулярных выражений Х и У отношение ~ определяем следующим образом: Х ~ У (Х аппраксимирует У), если Х+ У У.
р Теорема. Отношение ~, определенное над рееулярными выражениями, являетея отношением порядка. Доказательство. Трапэитпвяость вмеет место, так как Х~ У, У аг Х+ У-У, У+Х-г. Поэтому Х+ г - Х+ (У+ г>-(Х+ У1+ г - У+ г - Х и, следовательво, Х ~ Я. Автисимметрнчвость имеет место, поскольку Х<У, Уа'Х «.У Х+У ° У+Х Х. Ре4лексиввость следует иэ Х+Х Х. е Отсюда также следует, что Х ч У «ЯХ ч ЯУ для регулярвых выражепий Х, У и Е, одвако детали доказательства оставим в качестве упражвевия. Перед тем как рассматривать уравнения, иапомвим, что иэ опредслевив операции эамыкавия следует СО А*=А»+А'+ ...
+А" + ... = лч.", А", е» 22 д кто г, в«з» где Аз (. Зто соотношение оказывается полезпым при доказательстве следующих утверждений. Л е и м а. Пусть У и Š— решения регулярного урав- нения Х АХ+ В. Тогда а) В<У, б) АУ-'=- У, в) У+ Я вЂ” решение. Доказательство. а) Так как У вЂ” решепие уравнеппя Х= АХ+В, то У = АУ+ В, и поэтому У+В=(АУ+В)+В-АУ+(В+В)-АУ+В-У, Следовательпо, В ( У. б) Аналогично У+АУ=(В+АУ)+АУ=В+АУ У. Следовательно, АУ ~ У. в) Имеем У+У=АУ+В+АЗ+В=А(У+ Я)+В.
Р Уже достаточпо много сказаво о свойствах решепий уравпевия, одпако существует ли хотя бы одно решепиет Лемма. Аев является решением уравнения Х АХ+ В. Доказательство. Подставляя А*В в ураввепие, имеем ОО А(Аев)+ В =(ААе+ Ае)В= А ~~ А" + А' В ь=г ~А" ( Ао В ~ч~ А" В АеВ Теорема. А*В является наименьшим (но отношению к <) решением регулярного уравнения Х АХ+В, Доказательство. Из лемм следует, что Аев— решение, и если У вЂ” какое-либо другое решение, то В ~ У, АВ~АУ = У. Поэтому АВ~ У, А"В(У, и, добавляя неравенства для всех и ш г(0 (О), получаем Аев < У, Следовательно, утверждеияе теоремы верно.
Р Заметим, что Аев — это множество строк, каждая из которых является решением уравпеиия; если А (а) и В = (Ы, то все строки вида а Ь также являются решениями. Заметим также, что так как Аев является иаимепьшим решевием уравнения Х = АХ+ В, то оио является наименьшим выражением таккм, что Х ° АХ+ В совпадает с тождественным отображением. Поэтому его также 338 называют наименьшей стационарной точкой уравнения (или минимальной стационарной точкой), Рассмотрев одно частное уравнение, мы сейчас можем непосредственно получить аиалогичвые результаты для других похожих уравнений; докааатвльсгва в этих случаях будем опускать.
Т в о р е м а. Для заданных регуляркых выражений Л и В уравнение Х АХ + В вквивалентно паре уравнений Х УВ У УА+1 в том смысле, что оки имеют одно и то же наименьшее решение, и гто решекие есть Х АэВ. э" Теорема. Для ваданных регулярных выралсен,й А и В уравнение Х АХ+ Вэквивалентно паре уравнений Х ВУ У АУ+1. (В этом случае обе системы наименьшее решение Х = ВАь.) г Эти дае теоремы позволяют нам преобразовывать правые линейные формы (Х- АХ+ В) в лввыв линейные формы (Х ХА+ В), которые соответствуют правым и левым рекурсиям внутри регулярных грамматик.
Детали етого соответствия даны в п. 3.2, однако сначала мы обобщим рваультаты ва системы алгебраических уравнений. Предположим, что Хн ..., Х. — неизвестные регулярные выражения и что Ае (1 < $, ) ~ ч) и Вк ..., „— иавестные регулярные выражения такие, что Х1 Х1Лн+ХгАг~+...+Х.А,~+Вь Х, Х,Аи+ ХгАг, +... +Х„А„, + Вь Х„Х1А ы + ХгЛг„+... + Х„А„„+ В . Теперь можно испольаовать операции, оиредвлвнпые на регулярных выражениях, чтобы ввести операции на мат- рицах иа регулярных выражений (С + В)п С + )Уп, (С)У)ц - Хс,ь)Уы, А 60 Сэ ~С"; и г С ь )л тогда и только тогда, когда Сч ~))в для всех Г, 7, 939 339 где С и гг — согласованные матрицы, элементы которых являются регулярными выражениями.
Обозначив через Х «регулярную матрицу«, мы можем представить приведенные выше уравнения в виде Х = ХА+ В. Применяя рассуждения, аналогичные тем, которые использовались в случае одного уравнения, иоя;но покааать, что эта систеиа имеет минимальную стационарную точку ВА», которая достигается на решениях Х В1', где 'г' Аг'+1; 1 — едипичпая матрица.
Соответствующие результаты справедливы для правых линейных систем. Из замечаний следует, что зти систеыы аквивалентны. Это помогает удалению левых рекурсий в контекстно-свободных граиматиках. Ясно, что для уравнения Х ° ХА+ В решение может быть определено как Х, =(Ву), -,'з В,у„в г где У» = (АУ + 1)ц = ~~ Ав УЫ + 1П Пример 4.4 гл. 8 показывает, как этот результат переносится на контекстно-свободные грамматики. Преобразования, используемые в этом примере (хотя они и не строго обоснованы), появились прн помощи рассуждений по аналогии. Мы завершаем этот раздел, указывая на формальную связь ыежду регулярной алгеброй конечных распоапавателей и регулярныин грал>иатнкаып.
3.2. Представления регулярных граыматпк. Напомним, в гл. 8 структурная грамматика С (>«', Т, Р, 8) называлась грамматикой Хамского типа 3 илв (Л-свободной) регулярной грамматикой, если все элементы Р имели ввд А- х нлп А- хВ, где х Т и А, Вшй, или же(если Л«и Ь(С)) Ю- Л; в этом случае В не встречается ни в какой правой части. Множество предков>ений, поро>кдеппых регулярной грамматикой, называют регулярным м>шжеством или регулярным языком. В настоящий иоыеет мы в состоянии обосновать использование дважды одной н той же терыинологии и, следовательно, использовать регулярную ал>ебру в грамматиках.
Основной результат состоит иа двух частей и дав в виде теоремы с кояструктивпым доказательством. Часть 1 является непосредственной, так как каждый пе- 340 реход опрсделя<от иа всей его области определепия; в части П не обязательно, чтобы грамматика (Л', Т, Р, Б) для данных Х <вЖ и а <и Т имела продукцию вида Х.+ а илп Х - а У и рв некотором У <и М, Т е о р о и а. Множество, представимое конечным автоматом, является в точности таким же, как если бы выводилось из регулярных грамл<атик.
Доказательство. Опвшем копструкции доказательства. Вначале рассмотрим конечный автомат М (С, Е, г, д, Р). Теперь построим регулярную грамматику С (<У, Т, Р, Б). Если Л ФА(М), то можно сделать следующее. Пусть <т' Д, Т-Е и Б о; построим Р такое, что Р (Х- аУ, У<вг(Х, а)) 0(Х- а, 1(Х„а)ПР<вд<). Если Л ее А(М), то расширяем конструкцию, создавая новый нетермипал д, полагая Б — д и добавляя к Р продукции Б- Л, Б- аУ (если Ую<(д, а)), Б- а (если 1(о, а)ПР д<). Сейчас легко показать, что для каждого х мХе условие х<и А(М) выполнено тогда и только тогда, когда х <в <в ЫС). Очевидпо, что если д ю Р, то Л представимо автоматом М и Б - Л вЂ” продукция С и наоборот, Если таки<в а ю А (М) и ! а! * л, то а* а<аз...а„,а,евЕ, в позтому существует путь в гра$е М, как показано па аел ап ~ ~< ,4 ч Рвс.
9А9 рис. 9А9. Здесь А,ее Ф (ие обязательио все различиы) и В <и Р, и по построевию (Б а<А<, Л< а<Ах, ..., Л з а„„<Л <, Л„< а„~ыР (рис. 9.20). Таким обрааом, а<в Ь(С). Проводя рессуя<пения в обратпом порядке, аналогично получаем ~(С)гл ы А ( о), в, следовательпо, равепство доказало. Сейчас надо показать, что для данной (Л-свободной) регулярной грамматики предложения атой грамматики могут быть предстзвимы некоторым конечным автоматом, а все другие строки не представимы этим автоматом. Возьмем 61 (№, Ть Рп Я~) и построим М~ (Дь Хо тп рм Р1), как показано далее. Пусть Х~ Т1 и ф аг ~л„ Ряс. 9.20 Рас. 9.2$ № 0(т) 0(я) (где т и я — специальные символы, которых иот в У1,' т представляет правильную термииальиую строку, а я представляет ошибку), В 8~ и Р~ (т).
Если также Лж Е(С~), т. е Я~ - Л принадлежат Рь то Р~ ° (т, д1). Окончательно имеем т~ (((Х, а), У): Х- аУ есть в Р~) 0 0 (((Х, а), т): Х- а есть в Р1)0 0 (((т, а), и) для всех а ш Е~) 0 0(((Х, Ь), к): если Х и № и не Х - ЬУ для любого У ж ш № и ае выполияетсл условие Х - Ь есть в Р~) 0 0 (((и, а), я) длл всех а ш Х~). Обоснование того факта, что зта машина представляет Ь(С~), оставляем в качестве упражнения.
г' Пример 3.3. Пусть задана регулярная грамматика б (1А, В, С, Ю, (х, у, г), Р, А), где Р (А - Л1хВ~УС, В гВ!у! уС, С- хП, Р- у0~х). Используя описанную выше копструкцшо, получим машину, изображенную иа рис, 9.21. х 342 У и р а ж н е и и е 9.3. 1. Пусть заделы регулярные зырансения А, В, С я В такие, что А ~ С и В ~ С. Доказать, что а) А + Р ~ С+ Ю; б) АП ~ СВ; в) ВА ~ОС; г) А*-'С*;д) А+В~С. 2. 11сследовать, как преобразуются результаты и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
