dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 81
Текст из файла (страница 81)
X выталкивается извторого магазина S. Однако есть два исключения.i. Если второй магазин содержит только маркер дна (следовательно, X —пробел), то второй магазин не изменяется; M сдвинулась еще на одинпробел вправо.ii. Если Y — пробел, и первый магазин пуст, то этот магазин остается пустым. Причина в том, что слева от головки M находятся только пробелы;е) если M меняет X на Y и сдвигается влево, то S выталкивает символ с вершиныпервого магазина, скажем, Z, затем меняет X на ZY во втором магазине. Этоизменение отражает, что символ Z, ранее расположенный слева от головки M,теперь обозревается ею.
Как исключение, если Z является маркером дна, то Sдолжна поместить BY во второй магазин, не выталкивая ничего из первого.6. S допускает, если новое состояние M является допускающим. В противном случае Sимитирует еще один переход M таким же способом.8.5.3. Ñ÷åò÷èêîâûå ìàøèíûСчетчиковую машину можно представить одним из двух способов.1.Счетчиковая машина имеет такую же структуру, как и мультистековая (см.рис. 8.20), но вместо магазинов у нее счетчики. Счетчики содержат произвольныенеотрицательные целые числа, но отличить можно только ненулевое от нулевого.Таким образом, переход счетчиковой машины зависит от ее состояния, входногосимвола и того, какие из счетчиков являются нулевыми.
За один переход машинаможет изменить состояние и добавить или отнять 1 от любого из счетчиков. Однакосчетчик не может быть отрицательным, поэтому отнимать 1 от счетчика со значением 0 нельзя.2.Счетчиковая машина также может рассматриваться, как мультистековая машина соследующими ограничениями:8.5. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ Ñ ÎÃÐÀÍÈ×ÅÍÈßÌÈСтр. 361361а) есть только два магазинных символа, Z0 (маркер дна) и X;б) вначале Z0 находится в каждом магазине;в) Z0 можно заменить только цепочкой вида XiZ0 для некоторого i ≥ 0;г) X можно заменить только цепочкой вида Xi для некоторого i ≥ 0.
Таким образом, Z0 встречается только на дне каждого магазина, а все остальные символы (если есть) — это символы X.Для счетчиковых машин будем использовать определение 1, хотя оба они, очевидно,задают машины одинаковой мощности. Причина в том, что магазин XiZ0 может бытьидентифицирован значением i. В определении 2 значение 0 можно отличить от остальных, поскольку значению 0 соответствует Z0 на вершине магазина, в противном случаетам помещается X. Однако отличить два положительных числа невозможно, посколькуобоим соответствует X на вершине магазина.8.5.4.
Ìîùíîñòü ñ÷åò÷èêîâûõ ìàøèíО языках счетчиковых машин стоит сделать несколько очевидных замечаний.• Каждый язык, допускаемый счетчиковой машиной, рекурсивно перечислим. Причина в том, что счетчиковые машины являются частным случаем магазинных, амагазинные — частным случаем многоленточных машин Тьюринга, которые потеореме 8.9 допускают только рекурсивно перечислимые языки.• Каждый язык, допускаемый односчетчиковой машиной, является КС-языком.
Заметим, что счетчик, с точки зрения определения 2, является магазином, поэтомуодносчетчиковая машина представляет собой частный случай одномагазинной,т.е. МП-автомата. Языки односчетчиковых машин допускаются детерминированными МП-автоматами, хотя доказать это на удивление сложно. Трудность вызывает тот факт, что мультистековые и счетчиковые машины имеют маркер $ вконце входа. Недетерминированный МП-автомат может “догадаться”, что он видит последний входной символ, и следующим будет маркер.
Таким образом, ясно, что недетерминированный МП-автомат без концевого маркера может имитировать ДМП-автомат с маркером. Однако доказать, что ДМП-автомат без концевого маркера может имитировать ДМП-автомат с маркером, весьма трудно, и мыэтого не делаем.Удивительно, но для имитации машины Тьюринга и, следовательно, для допусканиялюбого рекурсивно перечислимого языка, достаточно двух счетчиков. Для обоснованияэтого утверждения вначале доказывается, что достаточно трех счетчиков, а затем трисчетчика имитируются с помощью двух.Теорема 8.14.
Каждый рекурсивно перечислимый язык допускается трехсчетчиковоймашиной.362Стр. 362ÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀДоказательство. Начнем с теоремы 8.13, утверждавшей, что каждый рекурсивноперечислимый язык допускается двухмагазинной машиной. С ее использованием намдостаточно показать, как магазин имитируется с помощью счетчиков. Предположим,магазинная машина использует r – 1 ленточных символов. Можно обозначить символыцифрами от 1 до r – 1 и рассматривать магазин X1X2…Xn как целое число по основанию r, т.е. этот магазин (его вершина, как обычно, слева) представлен целым числомXnrn–1 + Xn–1rn–2 + … + X2r + X1.Используем два счетчика для хранения целых чисел, представляющих каждый издвух магазинов. Третий счетчик используется для установки двух других. В частности,третий счетчик нужен при делении или умножении числа на r.Операции над магазином можно разделить на три вида: вытолкнуть верхний символ из магазина, изменить магазинный символ и поместить символ в магазин.
Переход двухмагазинноймашины может вовлекать несколько таких операций; в частности, замену верхнего символа Xцепочкой символов нужно разделить на замену X и затем помещение дополнительных символов в магазин. Эти операции выполняются над магазином, который представлен числом i,следующим образом.
Заметим, что для выполнения операций, требующих подсчета чисел от 0до r – 1, можно использовать конечное управление мультистековой машины.1.Для выталкивания из магазина нужно изменить i на i/r, отбрасывая остаток, которымявляется X1. Начиная с нулевого значения третьего счетчика, число i несколько разсокращается на r, а третий счетчик увеличивается на 1. Когда счетчик, первоначально имевший значение i, достигает 0, происходит остановка. Затем исходный счетчикувеличивается на 1 и третий счетчик уменьшается на 1 до тех пор, пока третий счетчик снова не станет нулевым. В этот момент счетчик, в котором вначале было i, содержит i/r.2.Для изменения X на Y на вершине магазина, представленного целым i, число i увеличивается или уменьшается на небольшую величину, заведомо не больше r.
ЕслиY и X рассматриваются как цифры, и Y > X, то i увеличивается на Y – X; если Y < X,то i уменьшается на X – Y.3.Для помещения X в магазин, содержащий i, нужно поменять i на ir + X. Вначале умножаем i на r. Для этого несколько раз уменьшаем значение i на 1 и увеличиваемтретий счетчик (который, как всегда, начинается с 0) на r. Когда исходный счетчикдостигнет 0, в третьем счетчике будет ir. Третий счетчик копируется в исходный ивновь обнуляется, как в п. 1.
Наконец, исходный счетчик увеличивается на X.Для завершения конструкции нужно инициализировать счетчики, чтобы имитироватьмагазины из их начального состояния, в котором они содержат только начальный символдвухмагазинной машины. Этот шаг реализуется путем увеличения двух основных счетчиков на некоторое число от 1 до r – 1, соответствующее начальному символу. 8.5. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ Ñ ÎÃÐÀÍÈ×ÅÍÈßÌÈСтр. 363363Теорема 8.15. Каждый рекурсивно перечислимый язык допускается двухсчетчиковоймашиной.Доказательство. С учетом предыдущей теоремы нужно лишь показать, как имитировать три счетчика с помощью двух. Идея состоит в том, чтобы представить три счетчика,скажем, i, j и k, одним целым числом.
Этим числом будет m = 2i3j5k. Один счетчик будетхранить это число, а второй использоваться в качестве вспомогательного для умноженияи деления m на одно из трех простых чисел 2, 3 или 5. Для имитации трехсчетчиковоймашины нужно реализовать следующие операции.1.Увеличить i, j и/или k. Для того чтобы увеличить i на 1, нужно умножить m на 2.
В теореме 8.14 уже показано, как умножить содержимое счетчика на константу r, используявторой счетчик. Аналогично j увеличивается путем умножения m на 3, а k — на 5.2.Различить, какие из чисел, i, j или k, равны 0. Для того чтобы выяснить, что i = 0,нужно определить, делится ли m без остатка на 2. Число m копируется во второйсчетчик с использованием состояния машины, чтобы запомнить, уменьшено m четное или нечетное число раз. Если m уменьшено нечетное число раз к тому моменту,когда оно стало равно 0, то i = 0.
В таком случае m копируется из второго счетчика впервый. Аналогично, равенство j = 0 проверяется путем определения, делится ли mна 3, а k = 0 — делится ли оно на 5.3.Уменьшить i, j и/или k. Для этого m делится на 2, 3 или 5, соответственно. В доказательстве теоремы 8.14 описано, как выполнить деление на любую константу с использованием дополнительного счетчика. Трехсчетчиковая машина не можетуменьшить число 0 (это ошибка, ведущая к останову без допускания), поэтому еслиm не делится нацело на соответствующую константу, то имитирующая двухсчетчиковая машина также останавливается без допускания.8.5.5. Óïðàæíåíèÿ ê ðàçäåëó 8.58.5.1.Неформально, но четко и ясно опишите счетчиковые машины, которые допускают следующие языки. В каждом случае используйте как можно меньше счетчиков, но не более двух:а) (∗) {0n1m | n ≥ m ≥ 1};б) {0n1m | 1 ≤ n ≤ m};в) (∗!) {aibjck | i = j или i = k};г) (!!) {aibjck | i = j или i = k или j = k}.8.5.2.364Стр.
364(!!) Цель этого упражнения — показать, что мощность односчетчиковых машинс маркером конца входа не превосходит мощности детерминированных МПавтоматов. L$ — это конкатенация языка L с языком, содержащим однуÃËÀÂÀ 8. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÌÀØÈÍ ÒÜÞÐÈÍÃÀединственную цепочку $, т.е. L$ состоит из всех строк w$, где w принадлежит L.Покажите, что если язык L$ допускается ДМП-автоматом, где $ — концевоймаркер, не встречающийся в цепочках из L, то L также допускается некоторымДМП-автоматом. Указание. Этот вопрос совпадает с вопросом замкнутостиязыков, допускаемых ДМП-автоматами, относительно операции L/a, определенной в упражнении 4.2.2. Нужно модифицировать ДМП-автомат P для L$ путемзамены каждого из его магазинных символов X всеми возможными парами(X, S), где S есть множество состояний. Если P имеет магазин X1X2…Xn, то построенный для L ДМП-автомат имеет магазин (X1, S1)(X2, S2)…(Xn, Sn), где каждое Si есть множество состояний q, в которых P, начав с МО (q, a, XiXi+1…Xn),допускает.8.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
