Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 75
Текст из файла (страница 75)
Здесь есть два важных исключения. 1. Если > = 1, то М переходит к пробелу слева отХ>. В этом случае >(Х>Х>...Х„(- РВУХ>...Х„. 2. Если >' = и и У = В, то символ В, заменяющий Х„>пзисоединяется к бесконечной последовательности пробелов справа и не записывается в следуюшем МО. Таким образом, Х>Х>" Х..»уХп (- Х>Х> ".Хл >РХ„ь Пусть теперь 4 у, Л) = (р, У, Я), т.е. головка сдвигается вправо. Тогда ХХ,...Х, »уХЛ;,>...Х„!- ХХ,...Х, >УРХ, >...Х„.
Этот переход отражает сдвиг головки в клетку > + 1. Здесь также есть два важнь>х исключении. 1. Если У= и, то (» ь 1)-я клетка содержит пробел и не является частью предыдущего МО. Таким образом, Х>Х>...Х„. »уХ„(- Х>Хи .. Х„> УРВ. 2. Если > =1 и У= В, то символ В, записываемый вместо Х>, присоединяется к бесконечной последовательности пробелов слева и опускается в следующем МО.
Таким образом, >уХ>Хз,,.Хи ! РЛ>." ~е. и Пример 8.2. Построим машину Тьюринга и посмотрим, как она ведет себя на типичном входе. Данная машина Тьюринга будет допускать язык (О"1" ( и В 1). Изначально на ее ленте записана Конечная последовательность символов О и 1, перед и за которыми находятся бесконечнь>е последовательности пробелов. МТ попеременно будет изменять О на Хи 1 на У до тех пор, пока все символы О и 1 не будут сопоставлены друг другу. 332 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА Более детально, начиная с левого конца входной последовательности, МТ циклично меняет О на Х и движется вправо через все символы О и У, пока не достигнет 1.
Она меняет 1 на У и движется вправо через все символы У и О, пока не найдет Х. В этот момент она ищет О непосредственно справа и, если находит, меняет его на Хи продолжает процесс, меняя соответствуюшую 1 на у. Если непустой вход не принадлежит 0 1, то МТ рано или поздно не сможет совершить следуюший переход и остановится без допускания. Однако если она заканчивает работу, изменив все символы О на Х в том же цикле, в котором она изменила последнюю ! на У, то ее вход имеет вид О" 1", и она его допускает.
Формальным описанием данной МТ является М= !!да, д„ дг, дь дг), !О, !), )О, 1,Х, У, В), б, дв В, (д~)), где б представлена в таблице на рис. 8.9. Рис. 8.9 Машина Тьюринга, допускающая~О"1и ! и > 1/ В процессе вычислений М часть ленты, на которой побывала ее головка, всегда содержит последовательность символов, описываемую регулярным выражением Л 0*У 1 . Таким образом, там есть последовательность символов Х заменивших О, за которыми идут символы О, еше не измененные наХ. Затем идут символы У, заменившие 1, и символы 1, еше ве замененные У.
За этой последовательностью еше могут находиться символы О и 1. Состояние да является начальным, и в него же переходит М, возврашаясь к крайнему слева из оставшихся символов О. Если М находится в состоянии д, и обозревает О, то в соответствии с правилами (см, рис. 8.9) она переходит в состояние дь меняет О на Хи сдвигается вправо, Попав в состояние дн М продолжает движение вправо через все символы О и У. Если М видит Х или В, она останавливается !"умирает").
Однако, если М в состоянии д~ видит 1, она меняет ее на У, переходит в состояние дг и начинает движение влево. Находясь в состоянии дг, М движется влево через все символы О и У. Достигая крайнего справа Х который отмечает правый конец блока нулей, измененных на Х, М возврашлется в состояние дг и сдвигается вправо. Возможны два случая. 1, Если М видит О, то она повторяет описанный только что цикл.
1.2. МАШИНА ТЬЮРИНГА 333 2. Если же М обозревает У, то она уже изменила все нули наХ. Если все символы 1 заменены У, то вход имел вид О" 1", и М должна допускать. Таким образом, М переходит в состояние дз и начинает движение вправо по символам К Если первым после У появляется пробел, то символов 0 и 1 было поровну, поэтому М переходит в состояние д, и допускает. Если же М обнаруживает еще одну 1, то символов 1 слишком много, н М останавливается, ие допуская. Если М находит О„то вход имеет ошибочный вид, и М также "умирает". Приведем пример допускающего вычисления М на входе 0011. Вначале М находится в состоянии д„обозревая О, т.е.
начальное МО имеет вид 900011. Полная последовательность переходов образована следующими МО. 9~00! ! ! — Х9~0! ! )- ЛЗ)д,! ! )- Хд~ОУ! !- г)гХОЛ !- Ха,ОУ! !- ХХа~У! !- ХХУа~! 1- ХХагУУ ) — Хагхуу 1- ХХд,УУ )- ХХУд,у )- ХХУУд,В )- ХХУУВ9,В Рассмотрим поведение Мна входе 0010, который не принадлежит допускаемому языку.
а00010 ! Х9!010 ! ХО9~10 ) Хагоуо ! — В ХОРО !- Хцдоуо !- Хмур Уо !- ХХКу!0 )- ХХУОВ,В Это поведение похоже на обработку входа 0011 до МО ХХКу,О, где М впервые обозревает последний О. М должна двигаться вправо, оставаясь в состоянии до что приводит к МО ХХ)од,в. Однако у М в состоянии д~ по символу В перехода нет, поэтому она останавливается, не допуская.
8,2.4. Диаграммы переходов для машин Тьюринга Переходы машин Тьюринга можно представить графически, как и переходы МП- автоматов. Диаграмма иереходое состоит из множества узлов, соответствующих состояниям МТ. Дуга из состояния д в состояние р отмечена одним илн несколькими элементами вида ХУ УР, где Хи У вЂ” ленточные символы, а Р— направление (В или й). Таким образом, если ЩХ) = (р, 1; Р), то отметка ХУУР находится на дуге из д в р. Направление на диаграммах представляется не буквами В и В, а стрелками < — и — з, соответственно. Как и в других видах диаграмм переходов, начальное состояние представлено словом "начало*' и стрелкой, входящей в это состояние.
Допускающие состояния выделены двойными кружками. Таким образом, непосредственно из диаграммы о МТ известно все, кроме того, какой символ обозначает пробел. В дальнейшем считается, что это В, если не оговорено иное. Пример 8.3. На рис. 8.10 представлена диаграмма переходов для машины Тьюринга из примера 8.2. Ее функция переходов изображена на рис. 8.9.
П Пример 8.4. Сегодня машины Тьюринга рассматриваются чаще всего в качестве "распознавателей языков*' или, что равносильно, "решателей проблем". Однако сам ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 334 Тьюринг рассматривал свою машину как вычислитель натуральнозначных функций. В его схеме натуральные числа представлялись в единичной системе счисления, как блоки из одного и того же символа, и машина вычисляла, изменяя длину блоков или строя новые блоки где-нибудь на ленте. В данном простом примере будет показано, как машина Тьюринга может вычислить функцию — ', которая называется лгонусояг (гпопца) или усеченной разностью (ргорег зиЬсгасгюп) и определяется соотношением /и — ' и = шах(т — л, 0), т.е. т — ' л есть /и — и, если т > л, и О, если т < и.
У/У- о/а- Начало У/У Рис. В. 10. Диаерамма переходов МТ, допускающая цепочки вида О"!" МТ, выполняющая эту операцию, определяется в виде М= ((г/, г/,, ..., г/,), (О, 1), (О, 1, В), б, г/, В). Отметим, что, поскольку МТ не используется для допускания входа, множество допускающих состояний не рассматривается. М начинает с ленты, состоящей из 0 10" и пробелов вокруг, и заканчивает лентой с т -' л символами О, окруженными пробелами. М циклически находит крайний слева из оставшихся 0 и заменяет его пробелом. Затем двюкется вправо до 1.
Найдя 1, М продолжает движение вправо до появления О, который меняется на 1. Затем М возвращается влево в поисках крайнего слева О, который идентифицируется после того, как М выходит на пробел и сдвигается вправо на одну клетку, Повторения заканчиваются в одной из следующих ситуаций. 1. В поисках 0 справа М встречает пробел. Это значит, что все л нулей в 0" изменены на 1, и и ч- 1 нулей в 0" заменены пробелами. Тогда М изменяет и ч- 1 единицу на пробелы и добавляет О, оставляя т — л нулей на ленте. Поскольку в этом случае т>л,тот — л=т — ' и. 8.2.
МАШИНА ТЬЮРИНГА 335 2. Начиная цикл, М не может найти О, чтобы заменить его пробелом, поскольку первые т нулей уже изменены на В. Это значит, что и > т, и и — ' и = О. М заменяет все ос- тавшиеся символы ! и О пробелами и заканчивает работу с пустой лентой. На рис. 8.11 представлены правила функции переходов 4 а на рис. 8.12 — ее диаграмма. Роль каждого из семи ее состояний описывается следующим образом.
Рис В !!. Мащина Тьюринга, вычисляющая функцию усеченной разности в/в- Начало О/О 1/1 О/О 1/В 1/В Рис. 8. !2 Диаграмма переходов для Л4Т из примера 8.4 336 ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА гг, — данное состояние начинает цикл и прерывает его, когда нужно. Если М обозревает О, цикл должен повториться. О меняется на В, головка сдвигается вправо, и М переходит в состояние дл Если же М обозревает 1, то все возможные соответствия между двумя группами нулей на ленте установдены, и М переходит в состояние дз для опустошения ленты. д~ — в этом состоянии М пропускает начальный блок из О в поисках 1.
Найдя ее, М пере- ходит в состояние дл ог — М движется вправо, пропуская группу из 1 до появления О. О меняется на 1, головка сдвигается влево, и М переходит в состояние оъ Однако возможно также, что после блока из единиц символов О уже не осталось. Тогда М в состоянии г7, обнаруживает В. Возникает ситуация 1, описанная выше, где л нулей второго блока использованы лля удаления л из т нулей первого блока, и вычитание почти закончено. М переходит в состояние о,, предназначенное для преобразования всех 1 в пробелы, а одного пробела — в О. дз — М движется влево, пропуская О и 1 до появления пробела. Тогда М сдвигается вправо и возвращается в состояние д~, начиная новый цикл. о, — вычитание закончено, но один лишний О ю первого блока был ошибочно заменен пробелом.
М движется влево, заменяя все 1 пробелами, до появления В. Последний меняется на О, и М переходит в состояние о„где и останавливается. пз — зто состояние достигается из г7ь если обнаруживается, что все О из первого блока заменены пробелами. В случае, описанном выше в 2, усеченная разность равна О. М заменяет все оставшиеся О и 1 пробелами и переходит в состояние йи о,— единственной целью этого состояния является разрешить М остановиться после выполнения работы. Если бы вычисление разности было подпрограммой другой, более сложной функции, то о~ начинало бы следующий шаг этого более объемного вычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
