Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 49
Текст из файла (страница 49)
4. В более сложной модели»>он<но учитывать условия, прн которых возможны ошибки при деончном сложении. Пример 2.3. Маш>ша, изобрая'епвая на рис. 9.11, также осуществляет двоичное сложение тем н1е самым 1О,ОВ О Рвс. 931 способом, что и в предыдущем случае, за исключением того, что она содержит два дополнительных состояния д» и с», которые проверяют наличие ошибок, связанных с внесением в знаковый бит и вынесением из знакового бита соответственно. Заключительные состояния д» и о> обозначают выходы, в которых либо произошли оба зти переноса одновременно, либо не произошел ни одвн из пих.
Следовательно, зтн выходы являются арифметически правильными. г Эти примеры показыва>от, что можно выполнить некоторые полезные преобразования и вычисления, однако остается открытым вопрос: насколько «сильными» являются конечные автоматыг В ответе иа этот вопрос встречаются две точки зрения. Первая, хотя и нетипичная, ваключается в следующем: можно заметить, что использованные в примерах алфавиты основывались лишь на двух символах. Мы можем использовать любой конечный алфавит, однако, как отмечалось в 2» гл. 8, алфавита размерности 2 всегда достаточно. Вторая точка зрения заключается в том, что общая доступная память в данное время в определенном компьютере является конечной, Коля она содержит и битов, то существует ровно 2" конечных состояний, в которых 21» 229 память может находиться.
Это число может быть большим, но оно всегда копечно (см. упражнение 9.2), и, следовательно, мы имеем конечную машину. 2.2. Недетермпнпроваввые машины. Рассмотрим с математической точки зрения, чтб могут делать этп абстрактные машппы. Чтобы упростить дело, е определении, данком выше, будем игнорировать функцию р. Следовательно, мы будем иметь дело только с устройствами, имеющимо копечное число состояний; будем их для краткости называть КР (ковечнымп распознавателями или акцепторамв). В дальнейшем будет удобно расширить область значений фувкции переходов з (см. определение) так, чтобы выполнялось условие з: ДхХ- У(()). Следовательно, вз даивого состояния под действием задавных входвьн зкачевий машина может иметь выбор, куда эдтв дальше. Это вичего ве добавляет к определению, однако обеспечпвает простой способ конструировав~я КР, который будет активно пспольаоваться в атом параграфе.
(1!ашпны такого типа называют недетериинированяыли КР. Чтобы еще более прояснить, дело для заданного КР М определим мвонсество строк, представимых машиной М (абозиачим это множество через А(М)), как указано вяже. Пусть М=((?, Е, Д оэ, Г) и зж Ев. Запшпем з в виде з-з1зз...з„и определим множество Т(з) ивдукцией по длине слова з следующим образом: Т(Л)- (ов) и Т(пз„)- () з(д,з„), эвт<ю где и з|...з, 1 для всех й, 1<й<я.
Таким образом, Т(з) — это множество всех ааключительвых состояний М, которые могут быть достигвуты под действием входной последовательности з. Если Т(з)())г И, то слово з представимо; поэтому множество строк, представимых мапшвой М, имеет впд А (М) (з: Т(з) () )г чь И). Недетермввировавиые КР полезны тем, что ови упрощают вадачу построения сложвых машин. Существевиым является то, что вам хотелось бы иметь возмоягность собрать машины вместе таким образом, чтобы ие было нужды, по крайней мере па первом этапе, касаться вопроса, 324 является или нет результат перехода функцией или отношением вад (гй Х Е) Х й,й. (Напомопм, что функция «е Х е'- дй(Р) соответствует отношению ЧХ й'- !«й.) Введение педетермипированиости не увеличивает потенциала КР.
Ог ведетермпнпроваппой машины всегда можно перейти к детерминированной, как будет показано в следующей теореме. Теорема. Для любого недетермипированного КР ЛХ! существует детерминированный КР Мй такой, что А (Лй !) А (Мй). Д о к а э а т е л ь с т в о. Дадим вначале общую схему доказательства. Пусть Л~! Ф!' 1' т!' Чй' 3)' Л~й Ый~ й' ~й' ЧО Рй)' Установим вначале, что й)й У(ч!) (в общем случае всо эти состояния нам будут не ну>ивы) н Е»=Е!. Для этого, начиная с дйю !;йй, рассмотрим множество всех состояний в г(ув, г!) (для г! «н Е!) п назовем это множество об- Р' разом ~!)„г!) функции гй, т.
е. мы переводим раэлпчиыо воэможности машины Лй! в единственное состояние машины Мй. Предполоншм, что далее мы читаем символ г!. В ЛХ! ето могло бы вызвать перевод состояния гй(дв, г!) в состоявпе иэ мвоясесгва йй(й! (дв, г!), гй). Миоясестэо всех состояний, полученных таким обравам, сейчас дает единственное состояние в Мь получающееся в результате прп- Ф мененпя гй к образу из (дй, г,) и гй. Таким образом, мы приходим к конструкции переходов между состояниями в Чй. Так как ()! конечно, то конечно и «)й; следовательно, необходимо вернуться к ранее построенным состояниям, и, таким образом, процесс в конце концов оборвется. Если одно пв «выбранных» состояний в Ч! было в Рй, то состояние в !,')й является заключительным и, следовательно лея«ит в Рй.
Перейдем к подробному доказательству. В соответст- Ф вин с описанной выше конструкцией дй = (д«), ~ й тй! ((ч! ° ° у«!) «) ~ О тй(ч! гй) ! й п (дя, ..., де)«и Рй тогда и только тогда, когда д»йи Р! при некотором к, й < й < у, Возвращаясь назад к определению множества А (М) для даввой машины ЛХй, мы можем расширить ~! и гй, Звэ чтобы получить Т~ и Т» так, как зто показало ниже: Т«(Л) = (Ч«), Т«(о»») = В Г«(д, ««), я«,<а> Т,(Л) = (д~). Т ( «) () Г«(7, »«) = Ю,(д, »ь), «ят ра) где Т»(а) (д) и а ю...г«-ь Поскольку А(М) (г: Т(»)П г"'«ь 81 я существует естественное соответствие между Р~ и Р»„то мы должны лишь продемонстрировать такое»се соответствие между Т~(г) и Т»(») для любого»; т. е.
(..., д~, ...) Т~(») тогда и только тогда, когда ((..., дь ...1)= Т»(г), Сделаем зто ипдукцпей по длине г. Если !»! О, то г Л, откуда Т, (Л) = И,), Т, (Л) = Я = ((;,)). Предположим теперь, что соответствие имеет место для всех строк о: ~а) ч: й — 1, и рассмотрим строку о»„. По предполоя«еняю индукции (..., дь ...) — Т~(о) тогда и только тогда, когда ((.
г дь,,)) Т« (О) ° Однако тогда, если д,юг~(дь».), то отсюда следует, что д, ю Т,(оа») и (по определевию г») ( ° ~ дь ° ° 1 ~и «2((. ° .~ дь . ° .1, 3«) Т»(08«) ° Из определения Т«и ~» следует, что все злементы из Т»(о»„) должны выводиться таким же образом; по»тому (...,дь ...1 Т~(ог„) тогда и только тогда, когда ((..., дь ...)1 Т»(о»„). Следовательно, Т,(г) для л«обого» ю Х» «соответствует» Т»(г), и по»тому А(М,)-(»: Т,(»)ПР,:а)- (: Т (»)()г" а) А(М ).,г Приведенная выше аргументация была достаточно сложной и включала некоторое сомнительное (однако строго определенное) понятие «соответствие», которое подравумевало уровень вложения включаемых множеств. В частных примерах мы можем обойти зто путем введения подходящих имен для результирующих состояний в детерминироваивой машине М».
1(ак будет показано в последующем примере, построение М» из М~ является яепосредствепныи, однако, чтобы сохранить математическую строгость, папомиим вначале 326 общепринятое соглашение, свяванное с функциями. В силу используемых построений такое соглашение было бы вдесь неуместным, однако краткое напоминание об втой погрешности послужит объяснением, «откуда берутся некоторые множества».
Пусть вадана функция (: А - В такая, что (: х у. Мы должны были бы писать Ях) = (у), однако часто запись сводится к 1(х) = у. Аналогично обычно детерминированный перенос обозначаем как где 1! (Д а) т 1(Д«, г) - Д! Однако, когда мы имеем 1! ДХ2- У(!Г) (как в М, н ЛГ»), то мы должны аавлючать множества в скобки даже тогда, когДа Й(Де а)) -1, и писать 1(Дь з) (Д,). ПеРейдем к примеру.
Пример 2.4. Возьмем ЛХ! таким, как указано на рис. 9.12,а. Тогда т!(До, х) (Д!, Дт) н д! «в Р!; следовательно, получаем (д!, д«) в Рь Аналогично »! (д! х) (д«) 1! (д» х) (д» дз) следовательно, !»((д!! Д2), х) (ДО~ Дн дз) В Л|2 и т. д. Окончательно получаем ситуацию, изображенную на ряс.
9.12, 6. Тогда перенумерацпя дает нам рнс. 9.12, с. У С етого момента мы не будем выяснять, какие машины рассматрпва«отея — детерминированные или нет; онп всегда могут рассматриваться как детерминированные. 2.3. Составные машины. Сейчас в«ы в состоянии описать, как ваданную совокупность КР можно «собрать вместе» для тоГо, чтобы получить некоторые корректно определенные множества строк. Основные свойства даны в виде предложенпя, однако вместо формальных доказательств мы дадим лишь описание включаемых в доказательство построений!. П р е д л о ж е н и е.
По заданным л!аш илам ЛГ! =(!?! 2, «3, Д, г3,), ЛГ«Я2, ь, 1н Р, г») ййт У Ряс. 922 лзьз лопеса построить теашииьз Лтз, ..., Мз такие, что А (Мз) = 1*~А (М,), А(М,) =А(М,) П А(М,), А(Мз) =А(Л~,РА(М,), А (Мз) = А (М~ ) о А (Мз), А(М,)-А(М,)А(М,), А (Мз) = Аз (М1). 328 Построение ЛХв. Машина Мв получается из М» заменой множества Р» заключительных состояний на мпожестзо ч»»»Рм Следовательно, Л14 =Я„Т, 2„9, (~»~Р»). Чтобы получить М», возьмем ч» — ч» Х Дз, возможпо, с некоторыми подходящимл переобозпачениями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
