1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 56
Текст из файла (страница 56)
Перенос стрелки обрывается естественным образом в соответствии с правилами а) и в). Б. Стрелка от В(а) после последовательности переносов через распоанаватели Л,,..., В, (1)1) опять вернулась на' вход В,. Зто означает, что распознаватели В,,..., В, образуют цикл. В этом случае рассмотрим распознаватель ВЩ). Если ()= — а, то плюс-стрелка от Вх(а) идет наверняка вдоль .цикла. Забудем на время плюс-стрелку от В(а) и начнем переносить плюс-стрелку от В,(ц). Естественно, что она пройдет ту же последовательность переносов, что и вначале стрелка от В(гх), т.
е. после серии переносов плюс-стрелка от Л,(а) попадает на вход В,(а). Таким образом, Л,(а) станет полуциклом, который .по теореме ТТ7 трансформируется в заглушку. Плюс-стрелка от Л(а) переносится на эту заглушку, которая по аксиоме Аб* раздваивается, после чего для порядка восстанавливается первоначальный внд распознавателя В,(а). Пусть ))опх=, 1. Тогда ай ()=88 илн ))ж881/у, где у — не. которая совершенная нормальная форма.
Применим к Л,((1) аасиому А2. Очевидно, что плюс-стрелка от Л,( (1)=Лд(а~/у) пойдет вдоль цикла В,,..., В,. Применив к В,(а1/у) аксиому АЗ, сведем дело к предыдущему случаю, после чего опять восстановим распознаватель Вг(а1/у) к виду Л1(р). Таким образом, мы добились того, что у каждого распознавателя, не являющегося заглушкой, плн>с-стрелка направлена илн .в заглушку, или в преобразователь, нлн в останов. 3-й ш а г .
Ликвидация циклов по минус-стрелкам. Очевидно, что после 2-го шага, если только в схеме остались циклы, то распоанаватели В„..., В,, образующие эти циклы, соединены друг с другом только минус-стрелками. Если 8=1, то такой полуцикл, ликвидируется по теореме ТТ8. Рассмотрим сначала правильный цикл В„..., Л„т. е.
цикл, не имеющий входов извне. В этом случае мы применпм к Л,(а) 27Я ГЛ. З. ИСЧИСЛЕНИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИИ аксиому А2 и расчленим поаксиомеАЗ ]аназлементарныеконьюякции. Все возникшие при этом плюс-стрелки будут вести к распознава- телюВ,ф). Поправилам шага 2 осуществим перенос этих плюс- стрелок. В результате Вхф) окажется без входных дуг и может быть уничтоя1ен по теореме ТТ6. Поскольку Л„..., Л, — правильный цикл, вслед за Лз могут быть последовательно уничтожены все распоанаватели, входящие в этот цикл, равно как и распознаватели, возникшие при расчленении В,.
Рассмотрим теперь любой цикл В„..., В„имеющий извне 1 входов. Возьмем любой из этих входов. Если этот вход идет от распознавателя, то после 2-го шага доказательства это может быть только минус-стрелка некоторого распознавателя В(а). Если вход идет от преобразователя, то по аксиоме А1* можно междунимициклом вставить распознаватель В(1). Применим к распознавателю В(а) аксиому А2 и по аксиоме АЗ расчленим его на элементарные коньюнкции. Все возникшие при этом плюс-стрелки будут входить в тот же распознаватель Л;(1(1~(г), в который ранее входила минус-стрелка от Л(а). По правилам шага 2 осуществим перенос Всех плюс-стрелок с распознавателя Вы Естественно, что по окончании переноса ни одна из этих плюс-стрелок не будет соединена ни с одним из распознавателей Л„..., В,. Таким образом, теперь цикл В„..., В, будет иметь | — 1 вход. Повторяя описанный процесс ликвидации входов в цикл (раз,получим в конце правильный цикл, который можно будет уничтожить по правилам предыдущего абзаца.
4-й ш а г . Ликвидация многих входов у распознавателей. Рассмотрим любой распознаватель В. Поскольку в схеме нет циклов, для него Всегда существует цепочка, ведущая от В либо к преобразователю, либо к останову, либо к ааглушке. Длина Ь(В))~0 максимальной такой цепочки конечна. Назовем Ь(Л) высотой В. Очевидно, что если от В к некоторому В' ведет дуга, то й(В))Ь(Л'). Рассмотрим теперь в схеме распознаватели, имеющие более одного входа, с максимальным значением высоты йам„, и применим к ним теорему ТТ4. В результате мы получим схему с максимальным значением высоты, равным й„,„— 1. Осуществляя последовательно этот процесс размножения распознавателей по теореме ТТ4, мы в конце концов получим схему, з которой все распознаватели, отличные от заглушек, будут иметь только по одному входу. Ликвидация нескольких входов в заглушки (не считая, конечно, входов, идущих от ннх самих же) делается по аксиоме Абэ.
Окончательная канонизация. 5-Й ш а г . ' Стандартизация цепочек. После 4-го этапа уже можно ааметить некоторое сходство преобраауемой схемы с канонической. На рис. 8.12 показан результат 4-го этапа для исходной схемы с рис. 7.9. Все распо- $ Вх.пОлнОтА исчислнния 279 знаватели схемы сгруппированы в правильные цепочки, соединенные минус-стрелками. Вход в цепочку идет либо от входной стрелки, либо от преобразователя. Минус-стрелка последнего распоанавателя ведет либо к преобразователю, либо к останову, либо на заглушку.
Сначала добьемся того, чтобы число цепочек в схеме в точности равнялось и+1, где п — число операторов. Для этого, если входная стрелка схемы или выходная дуга преобразователя непосредственно ведет к какому- либо преобразователю, применим к ней аксиому А1*, причем ялюс-стрелка вставленного 1Ркьт распознавателя Л(1) ведет, для .определенности, на останов. Теперь сделаем так, чтобы Адд т) Ды~7 минус-стрелка г последнего распознавателя каждой цепочки А)д) вела на заглушку. Коли г ведет ээ,7 к преобразователю, то по аксиоме А1* вставим на ее место РА7 Аг( ) распознаватель Л(1) с плюс- стрелкой, ведущей на заглушку.
Применяя аксиому А2, за- ~ж~ )т,РА ~7 меняем Л(1) на Л(1) с плюс- стрелкой, ведущей на оператор, и с минус-стрелкой, идущей на заглушку, и затем расчленяем Л(1) по аксиоме АЗ на элемен"тарные конъюнкции. Для обеспечения ортого- Рис. зл2. схема перед стаэдартинальности, пользуясь теоремой эазаев песочек. ТТ10, сгруппируем распознаватели вдоль каждой цепочки так, чтобы все распознаватели с одинаковыми элементарными конъюнкциями стояли рядом, образуя цепочку я. Применяя теоремы ТТЗ и ТТ6, уничтожим все распоанаватели, кроме первого, в каждой цепочке 9.
Теперь добьемся того, чтобы в кан'дой из в+1 цепочек присутствовали передачи управления на каждой из и операторов н на останов. Для этого по аксиоме А1" вставим в любом месте цепочки распознаватель Л(1) с плюс-стрелкой, ведущий на недостающий преобрааователь. После этого по теореме ТТ10 упорядочим распознаватели вдоль цепочки в соответствии с нумерацией операторов, т. е. в,таком порядке: А„,..., А„, останов, заглушки.
В результате этого упорядочивания все распознаватели с плюс- стрелками, ведущими на ваглушки, сгруппируются в конце цепоч- 280 ГЛ. Э. ИСЧИСЛЕВИЕ РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИИ кв. По теореме ТТ5 сделаем все заглушки вполне одииаковымн с условием, равным 1, и по аксиоме Аб соберем все заглушки в одну. В результате на концах цепочек смогут появиться распознаватели, обе выходные дуги которых ведут .в одно место. Устраним эти распознаватели по теореме ТТ2. Наконец по аксиоме АЗэ в каждой цепочке сгруппнруем в один распоэнаватель все элементарные конъюнкции, ведущие к одному и тому же оператору.
В результате шагов 1 — 5 мы получим матричную схему См, равносильную исходной схеме 6. 6-й ш а г. Обеспечение выполнимости. Добьемся сначала того, чтобы условия всех распоанавателей равнялись единице только на допустимых наборах. Для этого с помощью аксиом А7 — А10 построим стационарную верхнюю разметку схемы См и затем применим правило П1 к каждому иа распознавателей. Поскольку теперь для каждого Л(Р) имеет место Г~ФВ<Р>, желаемое достигнуто. Применением аксиом А7э — А10* разметка снимается со схемы.
После этого по аксиоме А1 вычеркнем нз схемы все распознаватели вида Л(1). В результате этого в схеме могут появиться. операторы, не имеющие входов. Вычеркнем эти операторы по аксиоме А4 и вслед за ними по теореме ТТ6 выходящие иэ них цепочки распознаватМЛВй: Осуществим теперь с помощью аксиом А11 — А14 стационарную нижнюю разметку В с помощью правила П2 эаблокируем все дэнн<ения по схеме с непродуктивными наборами.
По аксиоме Аб соберем все новые заглушки в одно место. Снова осуществим стационарную верхнюю раэметку н применим правило П1 к каждому иэ распознавателей. Удалим распознаватели с тождественно ложными условиями и, если окажутся, операторы беа входов. Поскольку в реэультате блокировки все непродуктивные наборы стали недопустимыми, после этого шага все распознаватели будут истинны только на допустимых и продуктивных наборах.
В реаультате изолированные фрагменты схемы, если они и остались, имеют вид правильных циклов, образованных одними операторами. Рассмотрим любой такой цикл и по аксиоме А1* заменим одну иа его дуг (А,, А;) распознавателем Л(1) с минус-стрелкой, идущей на Аг, а с плюс-стрелкой, идущей на ааглушку. По аксиомеА2эаменимегопа17($), у которого на ааглушку будет теперь идти минус-стрелка. Осуществив стационарную верхнюю разметку в этом фрагменте, применим к Л(1) правило П1, в результате чего он приобретет вид В(1). Убрав его по аксиоме А1, мы обнаружим, что выход иа А; идет на заглушку, а 'Аг остался беэ входа.
Рааомкнув таким обраэом цикл, мы смол<ем, применяя аксиому А4, начиная с Аы устранить весь изолированный фрагмент. й е.ь. ищв один историчкскин овзог 281 В случае необходимости после этой процедуры повторяется стандартизация цепочек распознавателей, реставрирующая матричный вид схемы. Теорема 5 доказана. ~'~ Т е о р е м а 6 (о полноте).
Любые две эквивалентные схемы Янова равносильны. Доказ ател ьство. Пусть По теореме 5 для схем С, и 6, существуют капопичегкпе схемы Ск и Ск соответственно, для которых (н (2> 6, — С~ли и 6, — С~кы (2) Очевидно, что Ск = Си =Си, так как если бы Ск чь Ск, то тогда в силу теорем 5 и 4 мы пришли ы1 (2) бы к противоречию с (1). Таким образом, (2) переписывается в виде 6, Ск и Са Ск, откуда по симметричности и транзитивности отношения равносильности получаем, что 6, 6,. туту 88.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
