Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 80
Текст из файла (страница 80)
Первая лента содержит вход и просматривается слева направо. Вторая лента используется дчя запоминания излишка нулей по отношению к единицам или наоборот в прочитанной части входа. Опишите состояния и переходы, а также неформальное предназначение каждого 8.4.6.
состояния. 8.4.7. В данном упражнении с помощью специальной 3-ленточной МТ реализуется магазин. 1. Первая лента используется только для хранения и чтения входа. Входной алфавит состоит из символа Т, который интерпретируется, как "вытолкнуть из магазина", и символов а и Ь, интерпретируемых как "поместить а (соответственно, Ь) в магазин'*. Машина Тьюринга должна начинать работу с пустым магазином и реализовывать последовательность операций помещения в магазин н выталкивания, заданных входом, читая его слева направо. Если вход приводит к тому, что МТ пытается вытолкнуть нз пустого магазина, то она должна остановиться в специальном состоянии ошибки д,.
Если весь прочитанный вход оставляет магазин пустым, то вход допускается путем перехода в заключительное состояние йя Опишите неформально, но четко и ясно функцию переходов данной МТ. Вкратце опишите предназначение каждого использованного состояния. 8.4.8. На рис. 8.17 была представлена имитация?г-ленточной МТ с помощью одноленточной в общем случае. а) (~) Предположим, что данная техника использована лля имитации 5-ленточной МТ, ленточный алфавит которой состоит из 7 символов. Сколько ленточных символов будет у одноленточной машины? б) (ь) Альтернативный способ имитации й лент с помощью одной состоит в использовании (?г + 1)-й дорожки для хранения позиций головок всех?г лент, причем первые ?г дорожек имитируют ?г лент очевидным образом.
Заметим, что с (А + 1)-й дорожкой нужно быть аккуратным, чтобы различать головки и ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА 354 2. Вторая лента используется для запоминания магазина. 3. Третья лента является выходной. Каждый раз, когда из магазина выталкивается символ, он записывается на выходную ленту вслед за ранее записанными. допускать возможность того, что две и более головок могут находиться в од- ной клетке. Сокращает ли данный метод число ленточных символов, необхо- димых для одноленточной МТ? в) Еще один способ имитации к лент с помощью одной вообще не требует запоминания позиций головок.
Вместо этого (й+ !)-я дорожка используется для отметки только одной клетки ленты. Каждая имитируемая лента все время позиционируется на своей дорожке так, что головка находится на отмеченной клетке. Если я-ленточная МТ перемещает головку на ленте 1, то имитирующая одноленточная МТ смешает все непустое содержимое Ьй дорожки на одну клетку в противоположном направлении, так что клетка, обозреваемая головкой )-й клетки в Ьленточной машине, остается в отмеченной клет- ке. Помогает ли данный метод сократить число ленточных символов одно- ленточной МТ? Есть ли у него недостатки по сравнению с другими описан- ными здесь методами? (!) Машина Тьюринга, называемая к-головочной, имеет к головок, читающих клетки на одной ленте.
Переход такой МТ зависит от состояния и символов, обозреваемых головками. За один переход эта МТ может изменить состояние, записать новый символ в клетку, обозреваемую каждой из головок, и сдвинуть каждую головку влево, вправо или оставить на месте. Поскольку несколько головок могут одновременно обозревать одну и ту же клетку, предполагается, что головки пронумерованы от 1 до й, и символ, который в действительности записывается в клетку, есть символ, записываемый головкой с наибольшим номером.
Докажите, что множества языков, допускаемых й-головочными и обычными машинами Тьюринга, совпадают. 8.4.9. 8.4.10. (В)Двухмерная машина Тьюринга имеет обычное конечное управление, но ее лента представляет собой двухмерное поле из клеток, бесконечное во всех направлениях. Вход помещается в одной строке поля, с головкой, как обычно, на левом конце входа и управлением в начальном состоянии. Вход допускается, как обычно, с помощью заключительного состояния. Докажите, что множества языков, допускаемых двухмерными и обычными машинами Тьюринга, совпадают. 8.5.
Машины Тьюринга с ограничениями 8.5. МАШИНЫ ТЬЮРИНГА С ОГРАНИЧЕНИЯМИ 355 Мы увидели обобщения манин Тьюринга, которые в действительности не добавляют никакой мощности в смысле распознаваемых языков. Теперь рассмотрим несколько примеров ограничений МТ, которые также не изменяют их распознавательной мощности.
Первое ограничение невелико, но подезно во многих конструкциях, которые мы увидим позже: бесконечная в обе стороны лента заменяется бесконечной только вправо. Ограниченным МТ запрещается также записывать пробел вместо других ленточных символов. Это ограничение позволяет считать, что МО состоят только из значащих сим- волов и всегда начинаются левым концом ленты. Затем исследуются определенные виды многоленточных МТ, которые обобщают МП-автоматьь Во-первых, ленты МТ ограничиваются и ведут себя, как магазины. Вовторых, ленты ограничиваются еше больше, становясь "счетчиками*', т.е, они могут представлять лишь одно целое число, а МТ имеет возможность только отличать 0 от любого ненулевого числа.
Значение этих ограничений в том, что существует несколько очень простых разновидностей автоматов, обладающих всеми возможностями компьютеров. Более того, неразрешимые проблемы, связанные с машинами Тьюринга и описанные в главе 9, в равной мере относятся и к этим простым машинам. 8.5.1. Машины Тьюринга с односторонними лентами Мы допускали, что ленточная головка машины Тьюринга может находиться как слева, так и справа от начальной позиции, однако достаточно того, что головка может находиться на ней или только справа от нее. В действительности, можно считать, что лента является бескаггечггайг а одну сторону, или односторонней (яешыпбпйе), т.е.
слева от начальной позиции головки вообще нет клеток. В следующей теореме приводится конструкция, показывающая, что МТ с односторонней лентой может имитировать обычную МТ с бесконечной в обе стороны лентой. В основе этой конструкции лежит использование двух дорожек на односторонней ленте. Верхняя дорожка представляет клетки исходной МТ, находящиеся справа от начальной позиции, и ее саму. Нижняя дорожка представляет позиции слева от начальной, но в обратном порядке. Точное упорядочение показано на рис. 8.!9.
Верхняя дорожка представляет клетки Х,,Хп ..., где Ха — начальная позиция головки, а Хп Х,, ... — клетки справа от нее. Клетки Х „Х,, и последующие представляют клетки слева от начальной позиции. Обратите внимание на * в левой клетке на нижней дорожке. Этот символ служит концевым маркером и предохраняет головку односторонней ленты от случайного выхода за левый конец ленты.
Рис. 8 !й Одггасгааранняя ггенгпа лгаакет иинтарааатн даустараннюю бесканечную лепту Можно усилить ограничение нашей машины Тьюринга, чтобы она никогда не записывала пробелов. Это простое ограничение, вместе с лентой, бесконечной только в одну сторону, означает, что лента всегда представляет собой префикс из непустых символов, за которым следует бесконечная последовательность пробелов. Кроме того, крайний слева непустой символ всегда находится в начальной позиции ленты. В теоремах 9.!9 и 10.9 будет видно, насколько полезно предполагать, что МО имеют именно такой вид. ГЛАВА 8. ВВЕДЕНИЕ В ТЕОРИЮ МАШИН ТЬЮРИНГА Теорема 8.12. Каждый язык, допускаемый МТ Мь допускается также МТ М, со следующими ограничениями. 1.
Головка М, никогда не смещается влево от своей начальной позиции. 2. М, никогда не записывает пробелы. Доказательство. Условие 2 обосновать легко. Введем новый ленточный символ В; выполняющий роль пробела, но отличный от него, Таким образом, если М имеет правило б,(9,Х) = (р, В, О), изменим его на Б,(9, Х) = (р, В; О). Положим 6>(д, В5 для любого состояния д равным б<(<7, В). Условие 1 требует больших усилий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
