XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 87
Текст из файла (страница 87)
Рис. 7.34 Итак, случай а = А в (7.9) проанализирован полностью. Пусть а ф А. Если при этом г Е Я', то, согласно предположению индукции, существует такое состояние г' Е Я', что в конечном автомате М' выполняется де ~„' г', при том что в М г' =~~ г. При г' = г, ввиду того что дуга (г, д) конечного автомата М, метка которой содержит символ а, останется и в конечном автомате М', получаем, что в М' Яе ~' г -+~ д, т.е. в М' де =«~ д. Д,7.1. Оооеиоааиие алгоритма детермиииаации 547 При г' ф г, т.е. в случае, когда г' =«+ г в конечном автомате М, заключаем, что в М существует тройка состояний г', т, д, такая, что г' =«~+ г и г -+а д.
По построению конечного автомата М' отсюда получаем, что г' ~а д в М'. Тогда в М' будет выполняться де =«д г' -+, д, т.е. де =«*, д (рис. 7.35). Случай г Е Я' тем самым полностью проанализирован. Π٠— -(3 Рис. 7.35 Если же г ф Я', т.е. состояние г удаляется при переходе к конечному автомату М', то тогда существует такое состояние р Е Я', что в М цепочка у читается на некотором пути длины гп < и — 1 из де в р, а из р в г ведет путь ненулевой длины по пустым дугам, т.е.
в конечном автомате М ое «Р~+» г (рис. 7.36). Тогда, согласно предположению индукции, в М' Чо ~я р', где р' =«1 р в М. Тогда опять в М возникает тройка состояний р', г, д, такая, что р' =«+ г и г -+» о (см. рис. 7.36). По построению конечного автомата М' в нем будет выполнено Р -+а 6 Итак, в М' ое =«я ф -+„д, т.е. в конечном автомате М' цепочка х читается на некотором пути из де в д: ее =«' е . н 548 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ ® 7~р) Рис. 7.36 2'.
Состояние д удаляется при удалении А-переходов, т.е. юФЯ'. В этом случае для некоторого г Е Я' будет выполняться ее =~' г =~~+ д в конечном автомате М, откуда, согласно результатам, доказанным для случая 1', де ~* г' в конечном автомате М для некоторого г~ е Ч~, такого, что в М г~ =~~ г. Следовательно, г'~А 7 =~~+ д в М, т.е. г' ~д д, что и требовалось доказать. Итак, мы полностью доказали, что любая цепочка х, читаемая в исходном конечном автомате М на некотором пути иэ начального состояния де в какое-то состояние е, читается также и в автомате М' на некотором пути иэ начального состояния де в такое состояние р, что в М имеет место р =~' д.
б. Докажем, что для любых состояния д Е Я' и цепочки х Е У' иэ того, что в конечном автомате М' цепочка х читается на некотором пути иэ начального состояния де в какое-то состояние д, т.е. имеет место де =~'. д, следует, что в исходном конечном автомате М цепочка х читается также на некотором пУтииэдевд: ее=~'ЧвМ. Д.7.1.
Обосиоаааие алгоритма детермиииаации 549 Проведем опять индукцию по длине пути в конечном автомате М', на котором читается цепочка х. Для пути нулевой длины доказываемое тривиально. Предполагая, что доказываемое верно для любой длины пути, не превосходящей и — 1, допустим> что в М' 9е =«" д. Тогда для некоторого г Е 17 в М' имеет место до =«„" 17 ~а д, причем да = х, атак как в М' нет Л-переходов, то а Е '>г, т.е.
а не может быть пустой цепочкой. Согласно предположению индукции, отсюда следует, что в М 9о ~„' г. Далее, из того, что в М' есть дуга из т в 9, на которой читается символ а, т.е. г -+ д в М', следует, что либо эта дуга есть и в исходном конечном автомате М, и тогда г -+а д в М, либо в М сУществУет такое состоЯние Р, что г ~~х Р -+о д. Как в том, так и в другом случае имеем до ~„' г ~+ 9 в конечном автомате М, т.е. в М цепочка х читается на некотором пути из начального состояния в состояние д: до =«' д.
в. Пусть цепочка х Е ЦМ), т.е. для некоторого заключительного состояния 1 Е Р цепочка х читается на некотором пути из начального состояния в состояние 1: 9о ~' 1. Тогда из п. а следует, что в М' цепочка х читается на некотором пути из Чо в такое состояние 1', что 1> =«~ 1 в М. Если 1> = 1, то 1> Е Р', если же 1' ~ 1, т.е. в М существует путь ненулевой длины по пустым дугам из 1' в 1, то, согласно определению множества Р У ЕР'. Итак, х6ЦМ').
Обратно, если х Е Ь(М'), т.е. в М' имеет место до =«' 1', где У Е Р', то, согласно п.б, 9о «а 1"> и в М. Но так как в множество Р' попадают либо заключительные вершины конечного автомата М, либо те его вершины, из которых заключительная вершина достижима по пустым дугам, то найдется такое У Е Р, что в М у> ~+ у и до =«' у> =«+ 1, т.е. 9е =«' 1 в конечном автомате М, откуда х Е Й(М). Итак, ЦМ) = Ь(М>), что и обосновывает корректность алгоритма удаления А-переходов. КОРректность алгоритма детерминизации. Пусть тепеРь М = (У, Я, до, Р, б) — исходный конечный автомат без 550 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ А-переходов, а М' = (К Я', дю г", о') — детерминированный конечный автомат, построенный согласно алгоритму, описанному в доказательстве теоремы о детерминизацин, т.е.
Я' = 2ч, Ю~е = (~о), Р' = (Я: Яй Р ~ З), и для любого Н С Ц и любого ае1' 6'(Б,а) = („) б(д,а). яел Мы должны доказать, что ЦМ) = ЦМ'). а. Докажем, что для любых цепочки х Е У" и состояния д Е Я ю того, что в М цепочка х читается на некотором пути иэ начального состояния де в какое.то состояние д, т.е. де «' д, следует, что эта цепочка читается и в М' на некотором пути ю состояния 1дс) в состполние-множестпво з', которое содержит д, т.е. в М' (де) «,".
з', где д Е о'. Доказательство проводим индукцией по длине пути в конечном автомате М, на котором читается цепочка х (так как в автоматах уже нет пустых дуг, т.е. А-переходов, то длина пути всегда совпадает с длиной цепочки, читаемой на этом пути; поэтому индукцию по длине пути в данном случае можно рассматривать как индукцию по длине цепочки). Случай пути длины нуль тривиален. Полагая доказываемое справедливым для всех путей, длина которых не больше п — 1, допустим, что цепочка я читается в М на некотором пути длины и ю ое в д, т.е.
де «" д. Тогда найдется такое г Е Я, что (7.10) Чо«„г +а% где з = уа и а Е У. Тогда, согласно предположению индукции, в конечном автомате М' цепочка у читается на некотором пути (цз) в такое В, что г е В: (де1 «„* В. Так как конечный автомат М' является детерминированным по построению, то из его состояния-множества В ведет дуга в некоторое состояние-множество з и метка этой дуги содержит символ а, т.е. В-+~ о' в М'. Докажем, что о Э у.
Состояние о = У(В, а) есть объединение всех множеств 6(р, а) при р Е В. В частности, при р = г множество д.7. К Обоеиоваиие алгоритма детермиивеаиии 551 остояний 6(г,а) в силу (7.10) содержит состояние д. Следоваельно, это состояние принадлежит и множеству Я,и тогда в М' имеет место ~до) =ья В~а Я, т.е. (до) «в 8Эд.
б. Докажем теперь, что для любой цепочки х Е У' и любого состояния з е Я' из Йо) ~в' Я в М' следует (Уд е Я)(до =ьв г) в М. Проведем индукцию по длине цепочки х. При ~х~ = О, т.е. для пустой цепочки х, утверждение выполняется тривиально. Пусть оно верно при всех й ( и — 1, и пусть (оо) =~" Я в М'. Отсюда для некоторого В Е Ц', т.е.
В С Я, в М' выполняется (до) ~ „" 1В-+и Я, причем х = да и а е У. Тогда, согласно предположению индукции, в М дс ~„' г для каждого т Е В. Поскольку Я = б'(В,а), то любой элемент о в Я есть элемент некоторого множества б(г,а) при г Е В, т.е. в М есть дуга г -+о д. Но, как мы только что доказали, для любого состоюпш г Е В имеет место до «'„г, т.е. для любого д Е Я имеем до ~„' г -+а д в конечном автомате М, откуда (Уд е Я) (М: до ~' д), что и требовалось доказать. в. Теперь, если х Е ЦМ), т.е.
цепочка х читается в М на некотором пути из начального состояния в одно из заключительных, а именно до =~в у для некоторого У Е Р, то, согласно Результатам, доказанным в п. а, в М' цепочка х читается на некотором пути из начального состояния в заключительное состояние Яу, содежащее вершину у: (до) =~' Яу Э У, т.е. Яу Е г" н х е ЦМ'). Обратно, если х Е ЦМ'), т.е.
1до) =о' Яу Е Р' в М', то для любого состояния о Е Яу будем иметь в конечном автомате М Яо =ьв д. Но состояние-множество Яу обязательно содержит и~которое заключительное состояние исходного конечного автомата М (состояние из подмножества Р). Тогда для любого такого состояния у Е Яу П Р получим оо =о' 7' в М> что и озна чает х е цМ). Итак, ЦМ) = ЦМ'), и тем самым вся процедура детерминнзации конечных автоматов полностью обоснована. 552 7. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ЯЗЫКИ Дополнение 7.2.
Конечные автоматы с выходом. Структурный синтез Пусть М= (т', чт, дв, г', б) — детперминироввнный конечный авптомепт. Модифицируем мешки его дуг, а именно фиксируем произвольно алфавита тт', который назовем выходным (хотя он может и совпадать со входным алфавшпом Ь' конечного автомата М), его буквы назовем выходными символами и для каждой дуги е конечного автомата М проделаем следующее: каждому входному символу а, принадлежащему метке дуги е, сопоставим однозначно упорлдоченнуто вару (а, Ь) е 'т" х тт'. Полученный таким образом размеченный ориенптированный граф называют конечным аетпомашом с выходом. Конечный автомат с выходом может быть определен и иначе, независимо от понятия детерминированного конечного автомата.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
