dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 77
Текст из файла (страница 77)
342ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ1.δ([q1, B], [B, a]) = ([q2, a], [*, a], R). В начальном состоянии M берет символ a(которым может быть 0 или 1), запоминает его в конечном управлении и переходит вуправляющее состояние q2. Затем “отмечает” обозреваемый символ, изменив егопервый компонент с B на *, и сдвигается вправо.2.δ([q2, a], [B, b]) = ([q2, a], [B, b], R). M движется вправо в поисках символа c. Напомним, что a и b независимо друг от друга могут быть 0 или 1, но не могут быть c.3.δ([q2, a], [B, c]) = ([q3, a], [B, c], R). Обнаружив c, M продолжает двигаться вправо, номеняет управляющее состояние на q3.4.δ([q3, a], [*, b]) = ([q3, a], [*, b], R).
В состоянии q3 продолжается пропуск всех отмеченных символов.5.δ([q3, a], [B, a]) = ([q4, B], [*, a], L). Если первый неотмеченный символ, найденныйM, совпадает с символом в ее управлении, она отмечает его, поскольку он являетсяпарным к соответствующему символу из первого блока нулей и единиц. M переходит в управляющее состояние q4, выбрасывая символ из управления, и начинаетдвижение влево.6.δ([q4, B], [*, a]) = ([q4, B], [*, a], L).
На отмеченных символах M движется влево.7.δ([q4, B], [B, c]) = ([q5, B], [B, c], L). Обнаружив символ c, M переходит в состояние q5и продолжает движение влево. В состоянии q5 она должна принять решение, зависящее от того, отмечен или нет символ непосредственно слева от c. Если отмечен, топервый блок из нулей и единиц уже полностью рассмотрен. Если же символ слева отc не отмечен, то M ищет крайний слева неотмеченный символ, запоминает его, и после этого в состоянии q1 начинается новый цикл.8.δ([q5, B], [B, a]) = ([q6, B], [B, a], L). Если символ слева от c не отмечен, начинаетсясоответствующая ветка вычислений.
M переходит в состояние q6 и продолжает движение влево в поисках отмеченного символа.9.δ([q6, B], [B, a]) = ([q6, B], [B, a], L). Пока символы не отмечены, M остается в состоянии q6 и движется влево.10. δ([q6, B], [*, a]) = ([q1, B], [B, a], R). Обнаружив отмеченный символ, M переходит всостояние q1 и движется вправо, чтобы взять первый неотмеченный символ.11.
δ([q5, B], [*, a]) = ([q7, B], [*, a], R). Теперь рассмотрим ветку вычислений, когда всостоянии q5 непосредственно слева от c обнаружен отмеченный символ. Начинается движение вправо в состоянии q7.12. δ([q7, B], [B, c]) = ([q8, B], [B, c], R). В состоянии q7 обозревается c.
Происходит переход в состояние q8 и продолжается движение вправо.13. δ([q8, B], [*, a]) = ([q8, B], [*, a], R). В состоянии q8 машина движется вправо, пропуская все отмеченные символы.8.3. ÒÅÕÍÈÊÀ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀСтр. 34334314. δ([q8, B], [B, B]) = ([q9, B], [B, B], R). Если M достигает пробела в состоянии q8, необнаружив ни одного неотмеченного символа, то она допускает.
Если же она сначала находит неотмеченный символ 0 или 1, то блоки слева и справа от c не совпадают,и M останавливается без допускания.8.3.3. ÏîäïðîãðàììûМашины Тьюринга — это программы, и их полезно рассматривать как построенные изнабора взаимодействующих компонентов, или “подпрограмм”. Подпрограмма машины Тьюринга представляет собой множество состояний, выполняющее некоторый полезный процесс.Это множество включает в себя стартовое состояние и еще одно состояние, которое не имеетпереходов и служит состоянием “возврата” для передачи управления какому-либо множествусостояний, вызвавшему данную подпрограмму.
“Вызов” подпрограммы возникает везде, гдеесть переход в ее начальное состояние. Машины Тьюринга не имеют механизма для запоминания “адреса возврата”, т.е. состояния, в которое нужно перейти после завершения подпрограммы. Поэтому для реализации вызовов одной и той же МТ из нескольких состояний можно создавать копии подпрограммы, используя новое множество состояний для каждой копии.“Вызовы” ведут в начальные состояния разных копий подпрограммы, и каждая копия“возвращает” в соответствующее ей состояние.Пример 8.8.
Построим МТ для реализации функции “умножение”. Наша МТ начинает с 0m10n1 на ленте и заканчивает с 0mn. Опишем вкратце ее работу.1.В начале каждого из m циклов работы лента содержит одну непустую цепочку вида0i10n10kn для некоторого k 7.2.За один цикл 0 из первой группы меняется на B, и n нулей добавляются к последнейгруппе, приводя к цепочке вида 0i–110n10(k+1)n.3.В результате группа из n нулей копируется m раз с изменением каждый раз одного 0в первой группе на B. Когда первая группа нулей целиком превратится в пробелы, впоследней группе будет mn нулей.4.Заключительный шаг — заменить пробелами 10n1 в начале, и работа закончена.“Сердцем” этого алгоритма является подпрограмма, которая называется Copy.
Онареализует шаг 2, копируя блок из n нулей в конец. Точнее, Copy преобразует МО вида0m–k1q10n10(k–1)n в МО 0m–k1q50n10kn. Переходы подпрограммы Copy представлены нарис. 8.14. Она заменяет первый 0 маркером X, в состоянии q2 движется вправо до появления пробела, копирует в эту клетку 0, и в состоянии q3 движется влево, пока не появится маркер X. На маркере она переходит вправо и возвращается в q1. Она повторяет данный цикл до тех пор, пока в состоянии q1 не встретит 1 вместо 0.
Тогда она используетсостояние q4 для обратной замены маркеров X нулями и заканчивает в состоянии q5.344Стр. 344ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀНачалоРис. 8.14. Подпрограмма CopyНачалоКопированиеРис. 8.15. Полная программа умножения использует подпрограмму CopyВся машина Тьюринга для умножения начинает в состоянии q0. Вначале она за несколько шагов переходит от МО q00m10n1 к МО 0m–11q10n1.
Необходимые переходы показаны на рис. 8.15 слева от вызова подпрограммы; в них участвуют только состояния q0 и q6.7Перед первым циклом i = m и k = 0. — Прим. ред.8.3. ÒÅÕÍÈÊÀ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀСтр. 345345Справа от вызова подпрограммы (см. рис. 8.15) представлены состояния q7–q12.
Состояния q7, q8 и q9 предназначены для получения управления после того, как Copy скопировала блок из n нулей и находится в МО 0m–k1q50n10kn. Эти состояния приводят кконфигурации q00m–k10n0kn. В этот момент опять начинается цикл, удаляется крайнийслева 0 и вызывается Copy для нового копирования блока из n нулей.Как исключение, в состоянии q8 МТ может обнаружить, что все m нулей замененыпробелами, т.е. k = m. В данном случае производится переход в состояние q10. Это состояние с помощью состояния q11 заменяет символы 10n1 в начале ленты пробелами, после чего достигается состояние останова q12. В этот момент МТ имеет МО q120mn, и ееработа завершена. 8.3.4. Óïðàæíåíèÿ ê ðàçäåëó 8.38.3.1.(!) Переделайте ваши машины Тьюринга из упражнения 8.2.2, используя преимущества техники программирования, обсуждаемой в данном разделе.8.3.2.(!) Обычные операции в программах типа машин Тьюринга используют “сдвиг”(“shifting over”).
Предположим, в текущей позиции головки нужно создать дополнительную клетку, в которую можно было бы записать некоторый символ.Однако изменять ленту таким способом нельзя. Придется сдвинуть содержимоеленты справа от головки на одну клетку вправо и затем вернуться к текущей позиции. Покажите, как выполнить данную операцию. Указание.
Зарезервируйтеспециальный символ для отметки позиции, в которую нужно вернуться.8.3.3.(∗) Постройте подпрограмму перемещения головки МТ из ее текущей позициивправо с пропуском нулей до достижения первой 1 или пробела. Если текущаяпозиция не содержит 0, то МТ останавливается. Можно предполагать, что ленточными символами являются только 0, 1 и B (пробел). Используйте полученную подпрограмму для построения МТ, допускающей все цепочки из 0 и 1, вкоторых нет двух 1 подряд.8.4. Ðàñøèðåíèÿ áàçîâîé ìàøèíû ÒüþðèíãàВ этом разделе представлены некоторые вычислительные модели, связанные с машинами Тьюринга и имеющие такую же мощность (в смысле распознавания языков), что ибазовая модель МТ, с которой мы работали до сих пор. Одна из них, многоленточнаяМТ, позволяет легко имитировать работу компьютера или других видов машин Тьюринга.
И хотя многоленточные машины не мощнее базовой модели, речь также пойдет об ихспособности допускать языки.Затем рассматриваются недетерминированные машины Тьюринга — расширение основной модели, в котором разрешается совершать любой из конечного множества переходов в данной ситуации. Это расширение в некоторых случаях также облегчает “прог346Стр. 346ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀраммирование” машин Тьюринга, не добавляя ничего к распознавательной мощности базовой модели.8.4.1.
Ìíîãîëåíòî÷íûå ìàøèíû ÒüþðèíãàМноголенточная машина Тьюринга представлена на рис. 8.16. Устройство имеетконечное управление (состояния) и некоторое конечное число лент. Каждая лента разделена на клетки, и каждая клетка может содержать любой символ из конечного ленточного алфавита. Как и у одноленточных МТ, множество ленточных символов включает пробел, а также имеет подмножество входных символов, к числу которых пробелне принадлежит.
Среди состояний есть начальное и допускающие. Начальная конфигурация такова.1.Вход (конечная последовательность символов) размещен на первой ленте.2.Все остальные клетки всех лент содержат пробелы.3.Конечное управление находится в начальном состоянии.4.Головка первой ленты находится в левом конце входа.5.Головки всех других лент занимают произвольное положение. Поскольку все ленты,кроме первой, пусты, начальное положение головок на них не имеет значения (всеклетки “выглядят” одинаково).Рис. 8.16.
Многоленточная машина ТьюрингаПереход многоленточной МТ зависит от состояния и символа, обозреваемого каждойголовкой. За один переход многоленточная МТ совершает следующие действия.1.Управление переходит в новое состояние, которое может совпадать с предыдущим.8.4. ÐÀÑØÈÐÅÍÈß ÁÀÇÎÂÎÉ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀСтр. 3473472.На каждой ленте в обозреваемую клетку записывается новый символ. Любой из нихможет совпадать с символом, бывшим там раньше.3.Каждая из ленточных головок сдвигается влево или вправо или остается на месте.Головки сдвигаются независимо друг от друга, поэтому разные головки могут двигаться в разных направлениях, а некоторые вообще оставаться на месте.Формальная запись переходов не приводится — ее вид является непосредственнымобобщением записи для одноленточной МТ, за исключением того, что сдвиги теперьобозначаются буквами L, R или S. Возможность оставлять головку на месте не была предусмотрена для одноленточных МТ, поэтому в их записи не было S.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
