9.4. ДВУСТОРОННИЙ ДЕТЕРМИНИРОВАННЫЙ МАГАЗИННЫЙ АВТОМАТ

Как только мы заподозрили, что существует алгоритм сложности распознающий, входит ли у в х, его уже нетрудно построить. Но что может заставить нас подозревать о существовании такого алгоритма? Одна из возможных причин возникает при изучении двусторонних детерминированных магазинных автоматов для краткости).

2ДМА представляет собой специальный тип машины Тьюринга, допускающей язык. Многие задачи распознавания образов можно переформулировать в терминах задач распознавания языков. Например, пусть язык {хсух, подцепочка

Рис. 9.16. Двусторонний детерминированный магазинный автомат.

цепочки х). Тогда распознавание того, входит ли у в х, эквивалентно распознаванию принадлежности цепочки языку В этом разделе мы покажем, что существует 2ДМА, способный распознать Хотя этот 2ДМА может затратить времени, но известна мощная техника моделирования, позволяющая промоделировать поведение данного 2ДМА на входной цепочке длины на РАМ, которая затратит на это шагов. В настоящем разделе мы подробно изучим эту технику моделирования.

2ДМА можно рассматривать как двухленточную машину Тьюринга, одна из лент которой используется в качестве магазинной памяти (рис. 9.16). 2ДМА имеет входную ленту, которую можно только читать и у которой самая левая клетка помечена концевым маркером а самая правая — концевым маркером Распознаваемая входная цепочка располагается между этими двумя концевыми маркерами по одному символу в клетке. Входные символы берутся из входного алфавита который по предположению не содержит Входная головка (на входной ленте) может за один шаг прочесть один символ и сдвинуться на одну клетку влево, вправо или остаться на месте. Мы предполагаем, что головка не может сойти ни с одного конца входной ленты; наличие концевых маркеров позволяет так писать функцию переходов, чтобы она никогда не сдвигала входную головку влево от и вправо от

Магазин — это стек, содержащий символы из магазинного алфавита Дно (нижняя клетка) магазина содержит специальный символ отмечающий основание стека. Мы предполагаем, что не принадлежит

Управляющее устройство всегда находится в одном из состояний, принадлежащих конечному множеству Работа машины определяется функцией переходов 6, которая для всякого и указывает действие машины в случае, когда управляющее устройство находится в состоянии входная головка обозревает символ вершине магазина расположен символ А. Возможны три типа действий машины:

При любом из этих действий машина переходит в состояние и сдвигает входную головку в направлении (здесь или О, что означает сдвиг на одну клетку влево, вправо или отсутствие сдвигов); В означает добавление символа В в вершину магазина; удаление самого верхнего символа из магазина.

Определение. Формально 2ДМА определяется как семерка

где

1) S - конечное множество состояний управляющего устройства,

2) - входной алфавит (не содержащий

3) магазинный алфавит (не содержащий

4) — отображение множества Значение если определено, имеет один из следующих типов: или где Мы считаем, что в заключительном состоянии не делает никаких шагов, для некоторых других состояний шаги работы могут быть не определены. Кроме того, для любых и А во второй компоненте не стоит во второй компоненте не стоит . Наконец, в третьей компоненте не стоит pop.

5) - начальное состояние управляющего устройства,

6) Z - маркер дна (нижний маркер) магазина,

7) S - выделенное заключительное состояние.

Мгновенным описанием на входе называется тройка где

1) s - состояние из S,

2) i — целое число, указывающее положение входной головки (считаем, что

3) а — цепочка, представляющая содержимое магазина, причем самый левый символ в а расположен в вершине магазина.

Шаг 2ДМА на входе агаг. определим с помощью бинарного отношения на

Заметим, что добавление, считывание и удаление символов происходит только в вершине магазина. Кроме того, требуется, чтобы в любой момент времени в магазине 2ДМА был только один маркер дна. Для обозначения последовательностей из нуля или более шагов 2ДМА используется знак рефлексивного и транзитивного замыкания отношения

Начальное мгновенное описание для (без концевых маркеров) имеет вид показывающий, что находится в своем начальном состоянии входная головка обозревает самый левый символ из агаг. и магазин содержит только нижний маркер

Допускающее мгновенное описание для имеет вид для некоторого показывающий, что автомат перешел в заключительное состояние и магазин содержит только нижний маркер.

Говорят, что допускает входную цепочку если при входе

для некоторого Языком допускаемым автоматом называется множество всех цепочек, допускаемых

Рассмотрим несколько примеров 2ДМА и допускаемых ими языков. 2ДМА будем описывать неформально — в терминах их поведения, а не как семерки.

Пример 9.11. Рассмотрим язык подцепочка цепочки может распознать следующим образом. Допустим, что автомату дана входная цепочка вида где .

1. P сдвигает свою входную головку вправо, пока не встретит с.

2. Р сдвигает свою входную головку влево, переписывая в магазин, пока входная головка не достигнет левого концевого маркера. В этот момент в магазине записано (самый левый символ цепочки расположен в вершине магазина).

3. Затем сдвигает свою входную головку к первому символу, стоящему справа от с (т. е. к началу цепочки не трогая магазин, и готовится сравнивать у с магазинным списком.

4. while символ в вершине магазина совпадает с символом, обозреваемым входной головкой

5. В этот момент возможны два случая.

(а) Входная головка достигла правого концевого маркера и тогда допускает вход.

(б) Символ в вершине магазина не совпадает с текущим входным символом. Поскольку цепочка у и магазинный список совпадали до сих пор, может восстановить магазинный список, сдвигая входную головку влево и переписывая вход в магазин, пока не встретит с. В этот момент в магазине автомата записана цепочка при некотором Если то останавливается в незаключительном состоянии. В противном случае удаляет из магазина и сдвигает входную головку вправо к первому символу цепочки Затем возвращается к шагу 4, пытаясь установить, не является ли у префиксом цепочки

Мы видим, что распознает, является ли у подцепочкой цепочки вполне естественным способом. пытается по очереди идентифицировать у с префиксом цепочки для Если это ему удается, он допускает вход. Если нет, отвергает. Заметим, что на эту процедуру может затратить шагов.

Пример 9.12. Рассмотрим язык где и (т. е. имеет префикс длины не менее 2, являющийся палиндромом). Здесь верхний индекс обозначает обращение цепочки; например, Требование наложено потому, что всякая цепочка из начинается с одного из тривиальных палиндромов или с. Рассмотрим 2ДМА Р, который на данной входной цепочке ведет себя следующим образом.

1. Р сдвигает входную головку к правому концевому маркеру, переписывая вход в магазин. Теперь магазин содержит Если то сразу отвергает вход.

2. Затем сдвигает входную головку к левому концевому маркеру, не трогая магазинный список. устанавливает входную головку на символ, стоящий непосредственно справа от левого концевого маркера.

3. while символ в вершине магазина совпадает с символом, обозреваемым входной головкой

4. В этот момент возможны два случая.

(а) Магазин содержит только и тогда останавливается и допускает вход.

(б) Символ в вершине магазина не совпадает с текущим входным символом. В этом случае сдвигает входную головку влево, переписывая вход в магазин, пока головка не достигнет левого концевого маркера. Если первоначальная входная цепочка имела вид то в этот момент в магазине автомата записано для некоторого Если то останавливается и отвергает вход. В противном случае удаляет из магазина и сдвигает входную головку на одну клетку вправо — к символу, стоящему непосредственно справа от левого концевого маркера. Затем возвращается к шагу 3.

Таким образом, устанавливает, начинается ли входная цепочка с палиндрома, пытаясь последовательно идентифицировать с префиксом цепочки для каждого На эту процедуру возможно, затратит шагов.

Покажем, что за время можно распознать, допускает ли 2ДМА Р входную цепочку независимо от того, сколько шагов в действительности делает На протяжении последующего обсуждения мы считаем фиксированными и входную цепочку длины

Определение. Поверхностной конфигурацией (для краткости конфигурацией) автомата называют такую тройку что положение входной головки, и А — один из магазинных символов из

Заметим, что конфигурация является МО, но не всякое МО является конфигурацией. В некотором смысле каждая поверхностная конфигурация представляет многие МО - те, у которых "поверхность", т. е. вершина магазина, совпадает с третьей компонентой

этой конфигурации. Говорят, что конфигурация выводима из конфигурации и пишут если найдется такая последовательность шагов автомата что при

где для каждого В этой последовательности шагов промежуточные имеют в магазине не менее двух символов. Мы будем оперировать с конфигурациями, а не с МО, потому что конфигураций только а число различных МО может быть экспоненциальным.

Определение. Конфигурацию называют терминальной, если значение не определено или имеет вид Иными словами, терминальная конфигурация приводит или к остановке автомата или к удалению символа из магазина. Терминатором конфигурации С называется такая единственная терминальная конфигурация С (если она существует), что где рефлексивное и транзитивное замыкание отношения

Пример 9.13. Если изобразить длину магазинного списка как функцию числа шагов, сделанных автоматом можно получить кривую типа кривой на рис. 9.17. На этом рисунке каждая точка помечена конфигурацией (не МО) автомата после каждого шага.

Из рис. 9.17 видно, например, что в конфигурациях в вершине стека находится Поскольку между этими конфигурациями нет конфигурации с в вершине стека, то Если заключительная конфигурация, то служит терминатором как для себя, так и для Из этого рисунка можно также вывести, что терминальная конфигурация, поскольку она приводит к тому, что удаляет символ из магазина.

Ключевые соображения для алгоритма моделирования содержатся в следующих двух простых леммах.

Лемма допускает тогда и только тогда, когда некоторая конфигурация вида служит терминатором начальной конфигурации

Доказательство. Результат вытекает прямо из определения того, что значит 2ДМА допускает входную цепочку.

Рис. 9.17. Последовательность конфигураций.

Определение. Конфигурацию С называют предшественницей конфигурации если и непосредственной предшественницей для если Говорят, что пара конфигураций лежит ниже пары (необязательно различных) конфигураций, если

т. е. если может дойти из с помощью шага а из с помощью шага

Лемма 9.2. Если лежит ниже и то

Доказательство. Легкое упражнение.

Пример 9.14. На рис. 9.17 пара лежит ниже пары а ниже Но нельзя сказать с уверенностью, что лежит ниже поскольку символы в вершинах магазинов для и могут быть различными.

Работа моделирующего алгоритма основана на поиске терминатора для каждой конфигурации 2ДМА Р при входе Как только найден терминатор начальной конфигурации цель достигнута.

Для хранения терминатора каждой конфигурации используется массив, называемый Мы предполагаем, что множество конфигураций линейно упорядочено (с помощью каких-то лексикографических условий). Тогда можно обращаться с именем С конфигурации как с целым числом и считать терминатором для С.

Используется также массив списков ПРЕД. Он индексируется конфигурациями, и список конфигураций С, для которых

Кроме массивов ТЕРМ и ПРЕД используются два дополнительных списка НОВ и ВРЕМ. Список НОВ содержит пары еще не

рассмотренных конфигураций для которых Список ВРЕМ нужен в процедуре чтобы хранить предшественниц конфигурации С.

Мы поступаем следующим образом. Сначала полагаем если С — терминальная конфигурация. (Каждая терминальная конфигурация является своим терминатором.) Добавляем к Затем рассматриваем такие пары что за один шаг работы (Заметим, что при таком шаге магазин не меняется.)

Если терминатор для уже известен, полагаем для всех о которых в этот момент известно, что они — предшественницы конфигурации С, включая саму С. (Собственные предшественницы находятся в Добавляем также пару к списку

Если терминатор для еще не известен, то С помещается в т. е. в список непосредственных предшественниц конфигурации

В этот момент для каждой конфигурации С известна такая единственная конфигурация что без изменения магазина, и либо терминатор для С, либо при Теперь рассматриваем все пары конфигураций, уже добавленные к списку . В общем случае НОВ содержит нерассмотренные пары конфигураций в которых терминальна. Допустим, что НОВ содержит пару Удаляем из НОВ и рассматриваем все пары конфигураций, лежащих ниже Если терминатор для уже вычислен, полагаем и добавляем к списку НОВ пару ТЕРМ. Для каждой конфигурации из полагаем и добавляем к списку Но если терминатор для еще не вычислен, помещаем С в список Продолжаем эту процедуру, пока НОВ не опустеет. В этот момент найден терминатор (если он существует) для каждой конфигурации С.

Исчерпав весь список рассматриваем где начальная конфигурация. Если допускающая конфигурация, то допускает . В противном случае отвергает

Дадим более точное описание.

Алгоритм 9.4. Моделирование 2ДМА

Вход. и входная цепочка

Выход. Ответ "да", если и "нет" в противном случае.

Метод.

1. Произведем начальную загрузку массивов и списков следующим образом. Для каждой конфигурации С положим Положим

Рис. 9.18. Процедура

2. Для каждой терминальной конфигурации С полагаем и добавляем к НОВ пару

3. Для каждой конфигурации С проверяем, существует ли такая конфигурация что за один шаг. Если да, вызываем Процедура приведена на рис. 9.18.

4. Пока список НОВ не пуст, удаляем пару из Для каждой пары лежащей ниже вызываем

5. Если где начальная конфигурация, является заключительной конфигурацией, получаем ответ "да". В противном случае "нет".

Пример 9.15. Рассмотрим некоторые вычисления, выполняемые алгоритмом 9.4, когда он применяется к 2ДМА, работающему, как показано на рис. 9.17.

На шаге 2 обнаруживаем, что терминальные конфигурации и потому свои же терминаторы. Добавляем к НОВ пары и

На шаге 3 вызываем Поскольку в этот момент то КОРРЕКТИР всего лишь помещает в список На шаге 3 вызываем также Так как то КОРРЕКТИР полагает

и добавляет к Кроме того, на шаге 3 вызываем и этот вызов полагает и добавляет к Поэтому после шага содержит пары

На шаге 4 удаляем из НОВ и вызываем поскольку лежит ниже Поскольку в этот момент полагает и добавляет к Затем на шаге 4 удаляем из поскольку (предположим, что это так) ниже не лежит никакая пара, не вызываем Аналогично не вызываем КОРРЕКТИР для пар Когда удаляется из вызываем и этот вызов полагает и добавляет к В этот момент НОВ содержит и

Удалив из вызываем что приводит к поскольку содержит Добавляем и к

Предлагаем читателю завершить это моделирование.

Теорема 9.10. Алгоритм 9.4 правильно отвечает на вопрос "Принадлежит ли слово языку за время

Доказательство. Можно показать, что каждая конфигурация попадает в список ВРЕМ не более одного раза. Поэтому каждый вызов процедуры КОРРЕКТИР закончится. Также можно показать, что никакая пара конфигураций не попадает в список НОВ более одного раза, следовательно, и сам алгоритм закончит работу. Подробное доказательство этих двух утверждений оставляем в качестве упражнения.

Покажем, что по окончании работы алгоритма будет заключительной конфигурацией тогда и только тогда, когда Легко показать индукцией по числу шагов работы алгоритма 9.4, что

1) если полагается равным то терминатор для С,

2) если С добавляется к то

3) если помещается в то

Таким образом, если алгоритм 9.4 обнаруживает, что заключительная конфигурация, то в силу леммы 9.1 утверждение верно.

Кроме того, надо показать, что если терминатор для С, то в конце концов становится равным Доказательство

проводится индукцией по числу шагов в последовательности Базис, т. е. случай нулевого числа шагов, тривиален, поскольку и делается равным на шаге 2 алгоритма 9.4.

Для шага индукции предположим, что и рассмотрим отдельно два случая.

Случай конфигурация, т. е. шаг не является ни шагом ни шагом Тогда на шаге 3 вызывается Если к этому моменту было присвоено значение то конфигурация С будет помещена в список ВРЕМ в строке 2 и в конце концов значение сделается равным в строке 5. Если значение еще не равно то добавляем С к в строке 1 процедуры По предположению индукции мы в конце концов получим, что Если это случится в строке 5 процедуры КОРРЕКТИР, то С добавится к ВРЕМ в строке 7, а значение сделается равным во время этого вызова процедуры КОРРЕКТИР. Значение не может стать равным на шаге 2 алгоритма 9.4, поскольку (Если бы оказалось, что то уже было бы присвоено значение к тому моменту, когда мы стали рассматривать на шаге 3.) Итак, в случае 1 значение оказывается равным

Случай это такое МО, что является шагом Тогда можно найти такие конфигурации что лежит ниже причем каждый из этих переходов совершается за меньшее число шагов, чем переход (Конфигурация А служит "поверхностью" По предположению индукции, значение полагается равным В, а значение равным

Допустим, что последнее происходит раньше первого. Тогда со временем помещается в а на шаге 4 вызывается Так как в этот момент то в строке 5 полагаем

Допустим теперь, что присвоено значение В до того, как присвоено значение Тогда при вызове и С добавляется к Но тогда становится значением при вычислении Это завершает индукцию и доказательство корректности алгоритма 9.4.

Проанализируем время работы алгоритма 9.4. Шаги 1 и 2 занимают времени, поскольку всего конфигураций Так как для каждой конфигурации 2ДМА делает не более одного шага, то пар конфигураций в которых всего Поэтому процедура КОРРЕКТИР вызывается на шаге 3 не более раз.

Пара попадает в список когда и уже найдено, что терминатор для С. Так как каждая конфигурация имеет лишь один терминатор (если она его вообще имеет), то никакая пара не помещается в список НОВ более одного раза.

Следовательно, общее число пар, помещаемых в список не превосходит Ниже каждой пары, попавшей в лежит ограниченное число пар, ибо если лежит ниже то положения головок конфигураций а также различаются не более чем на 1. Поэтому КОРРЕКТИР вызывается раз.

Теперь оценим общее время, затрачиваемое на подпрограмму КОРРЕКТИР. Можно показать, что в массиве ПРЕД каждая конфигурация появляется не более одного раза и в список ВРЕМ никакая конфигурация не попадает более одного раза. Общее время выполнения строк 4—б процедуры КОРРЕКТИР пропорционально количеству конфигураций В, удаляемых из ВРЕМ, а время выполнения строки 7 — количеству конфигураций А, добавляемых к ВРЕМ. Так как КОРРЕКТИР вызывается не более раз, то общее время, занимаемое процедурой КОРРЕКТИР, без учета времени на строки 4—6 и 7 составляет Следовательно, алгоритм 9.4 работает линейное время.

Результаты настоящего раздела применяются главным образом при доказательстве существования алгоритмов линейной сложности, решающих определенные задачи. Мы уже видели, что некоторые задачи идентификации образов можно сформулировать как задачи распознавания языков. Если мы сможем построить 2ДМА, распознающий язык, соответствующий задаче идентификации образов, то сможем утверждать, что существует алгоритм линейной сложности, решающий ту же задачу. Так как на входе длины 2ДМА может делать или даже шагов, то часто бывает проще найти алгоритм для распознавания языка на 2ДМА, чем алгоритм линейной сложности для решения задачи идентификации образов прямо на РАМ.