dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 79
Текст из файла (страница 79)
Цикл повторяется с шага 1.КонечноеуправлениеОчередь МОМО1∗ МО2x∗ МО3∗ МО4∗...Рабочая лентаРис. 8.18. Имитация НМТ с помощью ДМТОчевидно, что имитация точна в том смысле, что MD допускает только тогда, когданаходит, что MN может перейти в допускающее МО. Однако нужно обосновать, что еслиMN попадает в допускающее МО после n переходов, то MD в конце концов породит этоМО в качестве текущего и допустит.Предположим, что m есть максимальное число выборов у MN в любой конфигурации.Тогда существует одно начальное МО MN, не более m МО, достижимых за 1 шаг, не более m2 МО, достижимых за 2 шага, и т.д. Таким образом, после n переходов MN можетдостичь не более 1 + m + m2 + …+ mn МО, что не превышает nmn.Порядок, в котором MD исследует МО MN, называется “поиск в ширину” (“breadthfirst”), т.е.
она исследует все МО, достижимые за 0 переходов (начальное МО), затем всеМО, достижимые за 1 переход, за 2 перехода, и т.д. В частности, MD сделает текущимивсе МО, достижимые не более, чем за n переходов, и создаст все следующие за нимиМО, перед тем, как делать текущими МО, достижимые более, чем за n переходов.Как следствие, допускающее МО MN рассматривается MD в числе первых nmn МО.Нам нужно знать лишь то, что MD рассматривает это МО через некоторое конечное время, и этой границы достаточно, чтобы убедиться, что допускающее МО в конце концовдействительно рассматривается. Таким образом, если MN допускает, то MD также допускает.
Поскольку по построению MD допускает только потому, что допускает MN, можнозаключить, что L(MD) = L(MN). 352Стр. 352ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀОтметим, что построенная детерминированная МТ может потребовать времени, экспоненциально большего, чем время работы недетерминированной МТ. Неизвестно, является ли это экспоненциальное соотношение необходимым. Этому вопросу и некоторымего производным, связанным с поисками лучшего способа детерминированной имитацииНМТ, посвящена глава 10.8.4.5. Óïðàæíåíèÿ ê ðàçäåëó 8.48.4.1.Опишите неформально, но четко и ясно многоленточные машины Тьюринга,допускающие один из языков, приведенных в упражнении 8.2.2.
Постарайтесьпостроить каждую машину так, чтобы время ее работы было прямо пропорционально длине входа.8.4.2.Недетерминированная МТ M = ({q0, q1, q2}, {0, 1}, {0, 1, B}, δ, q0, B, {q2}) представлена следующей функций переходов.δ0Символ1Bq0{(q0, 1, R)}{(q1, 0, R)}∅q1{(q1, 0, R), (q0, 0, L)}{(q1, 1, R), (q0, 1, L)}{(q2, B, R)}q2∅∅∅Покажите, какие МО достижимы из начального МО, если входом является следующая цепочка:а) (∗) 01;б) 001.8.4.3.(!) Опишите неформально, но четко и ясно недетерминированные машины Тьюринга, возможно, многоленточные, которые допускают следующие языки.
Постарайтесь использовать преимущества недетерминизма, чтобы избежать итераций и сократить время работы в недетерминированном смысле, т.е. лучше, чтобы ваша машина имела много разветвлений, но ветви были короткими:а) (∗) язык всех цепочек из символов 0 и 1, содержащих некоторую подцепочкудлиной 100, которая повторяется, причем не обязательно подряд. Формально, данный язык есть множество цепочек из 0 и 1 вида wxyxz, где |x| = 100, аw, y и z имеют произвольную длину;б) язык всех цепочек вида w1#w2#…#wn для произвольного n, где каждая из wiесть цепочка из символов 0 и 1, причем для некоторого j цепочка wj являетсядвоичной записью числа j;в) язык всех цепочек того же вида, что и в п.
б, но хотя бы для двух значений jцепочки wj представляют собой двоичную запись j.8.4. ÐÀÑØÈÐÅÍÈß ÁÀÇÎÂÎÉ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀСтр. 3533538.4.4.(!) Рассмотрим недетерминированную машину ТьюрингаM = ({q0, q1, q2, qf}, {0, 1}, {0, 1, B}, δ, q0, B, {qf}).8.4.5.Неформально, но ясно опишите язык L(M), если δ состоит из следующих множеств правил: δ(q0, 0) = {(q0, 1, R), (q1, 1, R)}, δ(q1, 1) = {(q2, 0, L)}, δ(q2, 1) ={(q0, 1, R)}, δ(q1, B) = {(qf, B, R)}.(∗) Рассмотрим недетерминированную МТ, лента которой бесконечна в обоихнаправлениях. В некоторый момент времени вся лента пуста, за исключениемодной клетки, в которой записан символ $.
Головка находится в некоторой пустой клетке, а состоянием является q:а) напишите переходы, позволяющие НМТ перейти в состояние p, обозревая $;б) (!) предположим, что МТ детерминирована. Как бы вы позволили ей найти $и перейти в состояние p?8.4.6.Постройте следующую 2-ленточную МТ, допускающую язык всех цепочек из 0и 1, в которых этих символов поровну. Первая лента содержит вход и просматривается слева направо.
Вторая лента используется для запоминания излишканулей по отношению к единицам или наоборот в прочитанной части входа.Опишите состояния и переходы, а также неформальное предназначение каждогосостояния.8.4.7.В данном упражнении с помощью специальной 3-ленточной МТ реализуетсямагазин.1.Первая лента используется только для хранения и чтения входа. Входной алфавитсостоит из символа ↑, который интерпретируется, как “вытолкнуть из магазина”, исимволов a и b, интерпретируемых как “поместить a (соответственно, b) в магазин”.2.Вторая лента используется для запоминания магазина.3.Третья лента является выходной. Каждый раз, когда из магазина выталкивается символ, он записывается на выходную ленту вслед за ранее записанными.Машина Тьюринга должна начинать работу с пустым магазином и реализовывать последовательность операций помещения в магазин и выталкивания, заданных входом, читаяего слева направо.
Если вход приводит к тому, что МТ пытается вытолкнуть из пустогомагазина, то она должна остановиться в специальном состоянии ошибки qe. Если весьпрочитанный вход оставляет магазин пустым, то вход допускается путем перехода в заключительное состояние qf. Опишите неформально, но четко и ясно функцию переходовданной МТ. Вкратце опишите предназначение каждого использованного состояния.8.4.8.354Стр. 354На рис.
8.17 была представлена имитация k-ленточной МТ с помощью одноленточной в общем случае.ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀа) (∗) Предположим, что данная техника использована для имитации 5-ленточной МТ, ленточный алфавит которой состоит из 7 символов. Сколько ленточных символов будет у одноленточной машины?б) (∗) Альтернативный способ имитации k лент с помощью одной состоит в использовании (k + 1)-й дорожки для хранения позиций головок всех k лент,причем первые k дорожек имитируют k лент очевидным образом. Заметим,что с (k + 1)-й дорожкой нужно быть аккуратным, чтобы различать головки идопускать возможность того, что две и более головок могут находиться в одной клетке.
Сокращает ли данный метод число ленточных символов, необходимых для одноленточной МТ?в) Еще один способ имитации k лент с помощью одной вообще не требует запоминания позиций головок. Вместо этого (k + 1)-я дорожка используетсядля отметки только одной клетки ленты. Каждая имитируемая лента все время позиционируется на своей дорожке так, что головка находится на отмеченной клетке.
Если k-ленточная МТ перемещает головку на ленте i, то имитирующая одноленточная МТ смещает все непустое содержимое i-й дорожкина одну клетку в противоположном направлении, так что клетка, обозреваемая головкой i-й клетки в k-ленточной машине, остается в отмеченной клетке. Помогает ли данный метод сократить число ленточных символов одноленточной МТ? Есть ли у него недостатки по сравнению с другими описанными здесь методами?8.4.9.(!) Машина Тьюринга, называемая k-головочной, имеет k головок, читающихклетки на одной ленте. Переход такой МТ зависит от состояния и символов,обозреваемых головками. За один переход эта МТ может изменить состояние,записать новый символ в клетку, обозреваемую каждой из головок, и сдвинутькаждую головку влево, вправо или оставить на месте.
Поскольку несколько головок могут одновременно обозревать одну и ту же клетку, предполагается, чтоголовки пронумерованы от 1 до k, и символ, который в действительности записывается в клетку, есть символ, записываемый головкой с наибольшим номером. Докажите, что множества языков, допускаемых k-головочными и обычными машинами Тьюринга, совпадают.8.4.10. (!!) Двухмерная машина Тьюринга имеет обычное конечное управление, но еелента представляет собой двухмерное поле из клеток, бесконечное во всех направлениях.
Вход помещается в одной строке поля, с головкой, как обычно, налевом конце входа и управлением в начальном состоянии. Вход допускается, какобычно, с помощью заключительного состояния. Докажите, что множества языков, допускаемых двухмерными и обычными машинами Тьюринга, совпадают.8.4. ÐÀÑØÈÐÅÍÈß ÁÀÇÎÂÎÉ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀСтр. 3553558.5. Ìàøèíû Òüþðèíãà ñ îãðàíè÷åíèÿìèМы увидели обобщения машин Тьюринга, которые в действительности не добавляютникакой мощности в смысле распознаваемых языков. Теперь рассмотрим несколькопримеров ограничений МТ, которые также не изменяют их распознавательной мощности.
Первое ограничение невелико, но полезно во многих конструкциях, которые мыувидим позже: бесконечная в обе стороны лента заменяется бесконечной только вправо.Ограниченным МТ запрещается также записывать пробел вместо других ленточныхсимволов. Это ограничение позволяет считать, что МО состоят только из значащих символов и всегда начинаются левым концом ленты.Затем исследуются определенные виды многоленточных МТ, которые обобщаютМП-автоматы. Во-первых, ленты МТ ограничиваются и ведут себя, как магазины. Вовторых, ленты ограничиваются еще больше, становясь “счетчиками”, т.е.
они могутпредставлять лишь одно целое число, а МТ имеет возможность только отличать 0 от любого ненулевого числа. Значение этих ограничений в том, что существует несколькоочень простых разновидностей автоматов, обладающих всеми возможностями компьютеров. Более того, неразрешимые проблемы, связанные с машинами Тьюринга и описанные в главе 9, в равной мере относятся и к этим простым машинам.8.5.1. Ìàøèíû Òüþðèíãà ñ îäíîñòîðîííèìè ëåíòàìèМы допускали, что ленточная головка машины Тьюринга может находиться как слева, так и справа от начальной позиции, однако достаточно того, что головка может находиться на ней или только справа от нее. В действительности, можно считать, что лентаявляется бесконечной в одну сторону, или односторонней (semi-infinite), т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
