Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 77
Текст из файла (страница 77)
!.3 8.3.2, Многодорожечные ленты Еше один полезный прием состоит в том, чтобы рассматривать ленту МТ как образованную несколькими дорожками. Каждая дорожка может хранить один символ (в одной клетке), и алфавит МТ состоит из кортежей, с одним компонентом для каждой "дорожки". Например, клетка, обозреваемая ленточной головкой на рис. 8.13, содержит символ [Х У, 2]. Как и память в конечном управлении, множественные дорожки не расширяют возможностей машин Тьюринга. Это просто описание полезной структуры ленточных символов.
Пример 8.7. Типичное использование многодорожечных лент состоит в том, что одна дорожка хранит данные, а другая — отметку. Можно отмечать каждый символ, использованный определенным образом, или небольшое число позиций в данных. Данный прием фактически применялся в примерах 8.2 и 8.4, хотя лента там и не рассматривалась явно как многодорожечная. В данном примере вторая дорожка используется явно для распознавания следующего языка, который не является контекстно-свободным.
Ь„, .= (жси ) ч принадлежит(0+1) ) Построим машину Тьюринга м = (О, х, г, б, [д„в], [в, в], ([д,, в])), компоненты которой имеют следующий смысл. Д вЂ” множество состояний, которое представляет собой (оп ол ..., В,) х (О, 1, В), т.е. множество пар, состоящих из управляющего состояния д, и компонента данных О, 1 или В.
Вновь используется разрешенное выше запоминание символа в конечном управлении. à — множество ленточных символов (В, *) х (О, 1, с, В). Первый компонент, т.е. дорожка, может быть пустым или "отмеченным", что представлено, соответственно, пробелом или *. Символ * используется для отметки символов первой и второй групп из О и 1, в итоге подтверждаюшей, что цепочки слева и справа от центрального маркера с совпадают. Второй компонент ленточного символа представляет то, чем как бы является сам по себе ленточный символ, т.е.
[В, Х] рассматривается как ленточный символХдляХ= О, 1, с, В. Х вЂ” входными символами являются (В, О) и [В, 1], которые, как только что указано, обозначают, соответственно, О и 1. Б — функция переходов определена следующими правилами, в которых а и Ь могут обозначать как О, так и 1. ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 342 5 10.
12. з[4ч В), [В, а]) =([ул а], [*, а), В). В начальном состоянии М берет символ а (которым может быть 0 или 1), запоминает его в конечном управлении и переходит в управляющее состояние в)а Затем "отмечает" обозреваемый символ, изменив его первый компонент с В на *, и сдвигается вправо. 4[уа а], [В, Ь1) = ([дь а], [В, Ь), В). М движется вправо в поисках символа с. Напом- ним, что а и Ь независимо друг от друга могут быть 0 или 1, но не могут быть с. а([в)ь а], [В, с)) = ([в)в, а), [В, с], В), Обнаружив с, М продолжает двигаться вправо, но меняет управляющее состояние на йь ф[дв, а], [*, Ь)) = ([д„а], [в, Ь), В).
В состоянии Вв продолжается пропуск всех отмеченных символов. ~[дв, а), [В, а]) = ([а,, В], [*, а), Ь). Если первый неотмеченный символ, найденный М, совпадает с символом в ее управлении, она отмечает его, поскольку он является парным к соответствующему символу из первого блока нулей и единиц. М переходит в управляющее состояние д„выбрасывая символ из управления, и начинает движение влево, а([в)4, В), [*, а]) = ([ввл В], [", а), Ь). На отмеченных символах Мдвижется влево.
б([да В], [В, с1) = ([в)в, В], [В, с), Ь). Обнаружив символ с, М переходит в состояние ув и продолжает движение влево. В состоянии в)в она должна принять решение, зависящее от того, отмечен нли нет символ непосредственно слева от с. Если отмечен, то первый блок из нулей и единиц уже полностью рассмотрен. Если же символ слева от с не отмечен, то М ищет крайний слева неотмеченный символ, запоминает его, и после зтого в состоянии В, начинается новый цикл. х[0в В) [В а]) = ([Вв, В1, [В, а], 2). Если символ слева от с не отмечен, начинается соответствуюшая ветка вычислений.
М переходит в состояние дв и продолжает дви- жение влево в поисках отмеченного символа. с([д„В), [В, а]) =([~)в, В), [В, а], 2). Пока символы не отмечены, М остается в со- стоянии дв и движется влево. а([в2в, В), [*, а]) = ([дь В], [В, а], Л). Обнаружив отмеченный символ, М переходит в состояние дв и движется вправо, чтобы взять первый неотмеченный символ. х[Ф, В], [в, а]) = ([0ь В1, [*, а), В).
Теперь рассмотрим ветку вычислений, когда в состоянии ~)в непосредственно слева от с обнаружен отмеченный символ. НачинаетсЯ движение впРаво в состоЯнии Вь Ж7ъ В) [В, с]) = ([в2в В), [В, с), В). В состоянии В, обозревае вся с. Происходит пере- ход в состояние дв и продолжается движение вправо. в[ив, В1, [*, а)) = ([Вв В1, [*, а), В). В состоянии дв машина движется вправо, пропус- кая все отмеченные символы. 8.3. ТЕХНИКА ПРОГРАММИРОВАНИЯ МАШИН ТЬЮРИНГА 343 14. б!Ь1ж В), 1В, В]) = ([дп В], 1В, В), В). Если М достигает пробела в состоянии Е, не обнаружив ни одного неотмеченного символа, то она допускает. Если же она сначала находит неотмеченный символ 0 или 1, то блоки слева и справа от с не совпадают, и М останавливается без допускания.
8.3.3. Подпрограммы Машины Тьюринга — это программы, и их полезно рассматривать как построенные из набора взаимодействующих компонентов, или "подпрограмм". Подпрограмма машины Тьюринга представляет собой множество состояний, выполняющее некоторый полезный процесс. Зто множество включает в себя стартовое состояние и еше олно состояние, которое не имеет переходов и служит состоянием "возврата" для передачи управления какому-либо множеству состояний, вызвавшему данную подпрограмму. "Вызов" подпрограммы возникает везде, где есть переход в ее начальное состояние. Машины Тьюринга не имеют механизма для запоминания "адреса возврата", т.е. состояния, в которое нужно перейти после завершения подпрограммы.
Поэтому для реализации вызовов одной и той же МТ из нескольких состояний можно создавать копии подпрограммы, используя новое множество состояний для каждой копии. "Вызовы" ведут в начальные состояния разных копий подпрограммы, и каждая копия "возвращает" в соответствуюшее ей состояние.
Пример 8.8. Построим МТ лля реализации функции 'умножение'". Наша МТ начинает с 0" 10" 1 на ленте и заканчивает с 0 . Опишем вкратце ее работу. 1. В начале каждого из ги циклов работы лента содержит одну непустую цепочку вида 0'10" 10"" для некоторого Ь ~. 2.
За один цикл О нз первой группы меняется на В, и и нулей добавляются к последней группе, приводя к леночке вила 0' '10" 10'""" 3. В результате группа из и нулей копируется в раз с изменением каждый раз одного О в первой группе на В. Когда первая группа нулей целиком превратится в пробелы, в последней группе будет тп нулей. 4.
Заключительный шаг — заменить пробелами 10" 1 в начале, и работа закончена. "Сердцем" этого алгоритма является подпрограмма, которая называется Сору. Она реализует шаг 2, копируя блок из и нулей в конец. Точнее, Сору преобразует МО вида в г ~ а-1ж и ы 0 !д!010 " в МО 0 1дз010 . Переходы подпрограммы Сору представлены на рис. 8.14. Она заменяет первый 0 маркером Х, в состоянии пг движется вправо до появления пробела, копирует в эту клетку О, и в состоянии д, движется влево, пока не появится маркер Х. На маркере она переходит вправо и возвращается в дь Она повторяет данный цикл до тех пор, пока в состоянии д~ не встретит 1 вместо О. Тогда она использует состояние д, для обратной замены маркеров Х нулями и заканчивает в состоянии пп з 7 Перед первым циклом ! = я и й = О.
— Прим Реа ГЛАВА В. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 344 ! /1 О/О- !/! О/О- Начало «/ОРис. 8. !4. Подпрограмма Сору О/О Начала О О/В Рис. 8. !5. Полная программа умножения испол»»ует подпрограмму Сору 8.3. ТЕХНИКА ПРОГРАММИРОВАНИЯ МАШИН ТЬЮРИНГА 348 Вся машина Тьюринга для умножения начинает в состоянии с!е. Вначале она за несколько шагов переходит от МО !/»О 10" 1 к МО 0 '1!/!О" 1. Необходимые переходы показаны на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
