1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 75
Текст из файла (страница 75)
2ДМА можно рассматривать как двухленточную машину Тьюринга, одна из лент которой используется в качестве магазинной памяти (рис. 9.)б). 2ДМА имеет входную ленту, которую можно только читать и у которой самая левая клетка помечена концевым маркером й, а самая правая — концевым маркером Ч. Распознаваемая входная цепочка располагается между этими двумя конце. выми маркерами по одному символу в клетке. Входные символы берутся из входного алфавита т, который по предположению не содержит й и й. Входная головка (на входной ленте) может за один шаг прочесть один символ и сдвинуться на одну клетку влево, вправо или остаться на месте. Мы предполагаем, что головка не может сойти ни с одного конца входной ленты; наличие концевых маркеров й и Ч позволяет так писать функцию переходов, чтобы она никогда не сдвигала входную головку влево от й и вправо от 3.
Магазин — это стек, содержащий символы из магазинного алфавита Т. Дно (нижняя клетка) магазина содержит специальный символ л„отмечающий основание стека. Мы предполагаем, что ле не принадлежит Т. 314 ьл. двгстогоннип дмл Управляющее устройство всегда находится в одном из состояний, принадлежащих конечному множеству 5. Работа машины определяется функцией переходов 6, которая для всякого эЕ Я, а ~!О 0 (г, 8) и А Е ТО(Яь) уиазывает действие машины в случае, когда управляющее устройство находится в состоянии з, входная головка обозревает символ а и в вершине магазина расположен символ А.
Возможны трн типа действий машины: (э', й, рцз)э В), где Вчь2„ б (з„ а, А) = (з ") (в', й, рор), если А~Я,. При любом из этих действий машина переходит в состояние з' и сдвигает входную головку в направлении й (здесь й= — 1, +1 или О, что означает сдвиг на одну клетку влево, вправо или отсутствие сдвигов); рцзп В означает добавление символа В в вершину магазина; рор — удаление самого верхнего символа из магазина.
Определение. Формально 2ЛМА определяется как семерка Р=(В, (, Т, 6, з„г„;), где 1) Я вЂ” конечное множество состояний управляющего устройст ва, 2) ( — входной алфавит (не содержащий с и 3), 3) Т вЂ” магазинный алфавит (не содержащий Я,), 4) 6 — отображение множества (Я вЂ” (зД)х((О(р, Я) х (Т0 0 (Е,)). Значение 6(з, а, А)„если определено, имеет один из следующих типов: (з', й, рцзп В), (з', й) или (з', И, рор), где в'б5, ВЕТ ийЕ( — 1, О, +1). Мы считаем, что в заключительном состоянии з~ 2ДМА не делает никаких шагов, для некоторых других состояний шаги работы могут быть не определены. Кроме того, для любых з и А во второй компоненте у 6(з, г, А) не стоит й= — 1, во второй компоненте у 6(з, 3, А) не стоит й +1. Наконец, в третьей компоненте у 6(з, а, Е,) не стоит рор. 5) з,ЕЗ вЂ” начальное состояние управляющего устройства, 6) Яь — маркер дна (нижний маркер) магазина, 7) з~ — выделенное заключительное состояние.
А(гновенным описанием (МО) 2ДМА Р на входе и=а,а,...а„ называется тройка (з, 1, а), где 1) з — состояние из 5, 2) 1 — целое число, О-=1<а+1, указывающее положение входной головки (считаем, что а,=г и а„+,— — 3), 3) а — цепочка, представляющая содержимое магазина, причем самый левый символ в а расположен в вершине магазина. ГЛ. 9.
АЛГОРИТМЫ ИДЕНТИФИКАЦИИ Шаг 2ДМА на входе а,а,...а„определим с помощью бинарного отношения 1 — на МО: 1) (и, 1, Аа) ( — (з', 1+д, ВАа), если б (з, аь А)=(в', с(, рцв(т В), 2) (з, 1, Аа) )- (з', 1+д, Аа), если б(з, аь А)=(з', д), 3) (з, 1, Аа) )- (з', 1+д, ее), если Ь(в, аь А)=(в', д, рор). Заметим, что добавление, считывание и удаление символов происходит только в вершине магазина. Кроме того, требуется, чтобы в любой момент времени в магазине 2ДМА был только один маркер дна. Для обозначения последовательностей из нуля или более шагов 2ДМА используется знак рефлексивного и транзитивного замыкания )-* отношения 1 —.
Начальное мгновенное описание 2ДМА Р для ес=а,ае...а„(без концевых маркеров) имеет вид (в„1, Яе), показывающий, что Р находится в своем начальном состоянии з„входная головка обозревает самый левый символ из а,а,...а„а„+,') и магазин содержит только нижний маркер се.
Допускающее мгновенное описание для тс =а,...а„имеет вид (зь 1, 29) для некоторого 0~1(п+1, показывающий, что автомат Р перешел в заключительное состояние з~ и магазин содержит только нижний маркер. Говорят, что 2ДМА Р допускает входную цепочку ш, если при входе ес для некоторого Ъ 1((в(+1. Язьиам 1(Р), допускаемым автоматом Р, называется множество всех цепочек, допускаемых Р.
Рассмотрим несколько примеров 2ДМА и допускаемых ими языков. 2ДМА будем описывать неформально — в терминах их поведения, а не как семерки. Пример 9.11. Рассмотрим язык Ь (хсу)х,у~(а, Ь)' и у— подцепочка цепочки х). 2ДМА Р может распознать 1.
следующим образом. Допустим, что автомату Р дана входная цепочка тс вида хсу, где х=а,а,...а„и а~ ц (а, Ь), 1~1е~п. 1. Р сдвигает свою входную головку вправо, пока ие встретит с. 2. Р сдвигает свою входную головку влево, переписывая а„а„ ,...а, в магазин, пока входная головка не достигнет левого концевого маркера. В зтот момент в магааине записано хЕе=а,а,... ...а„29 (самый левый символ цепочки хне расположен в вершине магазина). ') Если п=о, т. е. вт в, то Р обозревает ое+з й, т. е. правый концевой маркер. в.с дпустопоннни дмл 3. Затем Р сдвигает свою входную головку к первому символу, стоящему справа от с (т.
е. к началу цепочки у), не трогая магазин, и готовится сравнивать у с магазинным списком. 4. 4и)зПе символ в вершине магазина совпадает с символом, обозреваемым входной головкой до Ьей)п удалить верхний символ из магазина; сдвинуть входную головку на одну клетку вправо епб 6. В этот момент возможны два случая. (а) Входная головка достигла правого концевого маркера $, и тогда Р допускает вход.
(б) Символ в вершине магазина не совпадает с текущим входным символом. Поскольку цепочка у н магазинный список совпадали до сих пор, Р может восстановить магазинный список, сдвигая входную головку влево и переписывая вход в магазин, пока не встретит с. В этот момент в МаГаЗИНЕ аВтОМата Р ЗаПИСаыа цЕПОЧКа ага4+т...а„24 Прн некотором 1(1<п '). Если 4'=и, то Р останавлйвается в незаключительном состоянии.
В противном случае Р удаляет а, из магазина и сдвигает входную головку вправо к первому символу цепочки уй. Затем Р возвращается к шагу 4, пытаясь установить, не является ли у префик- СОМ ЦЕПОЧКИ а4,...а„. Мы видим, что Р распознает, является ли у подцепочкой цепочки х а,аз...а„, вполне естественным способом. Р пытается по очереди идентифйцировать у с префиксом цепочки агаг+ь .,а„для 4= 1, 2, ..., л, Если это ему удается, он допускает вход. Если нет, отвергает. Заметим, что на эту процедуру Р может затратить ОЦх! ° ~у1) шагов. П Пример 9.12. Рассмотрим язык 1.=(гп1гп Е (а, Ь, с)*, ш=ху, где (х1 в2 н хи х) (т.
е. гп имеет префикс длины не менее 2, являющийся палиндромом). Здесь верхний индекс Й обозначает обращение цепочки; например, (аЬЬ)"=ЬЬа. Требование 1х!)2 наложено потому, что всякая цепочка из (а, Ь, с)+ начинается с одного из тривиальных палиндромов а, Ь или с. Рассмотрим 2ДМА Р, который на данной входной цепочке атаз...а„ведет себя следующим образом. 1.
Р сдвигает входную головку и правому концевому маркеру, переписывая вход в магазин. Теперь магазин содержит а„...аза424. Если п(2, то Р сразу отвергает вход. ') Когда мы попвдзем в тзнуюситувпиюпервый рвз, 1=1, ио впоследствии1 будет возрастать каждый рзз ив 1. гл, з ллгорнтмы идентиеикхции 2. Затем Р сдвигает входную головку к левому концевому маркеру, не трогая магазинный список.
Р устанавливает входную головку на символ, стоящий непосредственно справа от левого концевого маркера. 3. тгпВе символ в вершине магазина совпадает с символом, обозреваемым входной головкой йо Ьея1п удалить верхний символ из магазина; сдвинуть входную головку на одну клетку вправо ецио 4. В этот момент возможны два случая. (а) Магазин содержит только Ям н тогда Р останавливается и допускает вход.
(б) Символ в вершине магазина не совпадает с текущим входным символом. В этом случае Р сдвигает входную головку влево, переписывая вход в магазин, пока головка не достигнет левого концевого маркера. Если первоначальная входная цепочка имела вид а,а,...а„, то в этот момент в магазине автомата Р записано аь ..а,а,Е, для некоторого й Если (=2, то Р останавливается и отвергает вход. В противном случае Р удаляет а, из магазина и сдвигает входную головку на одну клетку вправо — к символу, стоящему непосредственно справа от левого концевого маркера. Затем Р возвращается к шагу 3.
Таким образом, Р устанавливает, начинается ли входная цепочка с палиндрома, пытаясь последовательно идентифицировать а;... ...а, с префиксом цепочки а,...а„для каждого (, 2(( 'л. На эту процедуру Р, возможно, затратит 0(п') шагов. П Покажем, что за время 0(~ш~) можно распознать, допускает ли 2ДМА Р входную цепочку ш, независимо от того, сколько шагов в действительности делает Р. На протяжении последующего обсуждения мы считаем фиксированными 2ДМА Р=(Б, 1, Т, 6, зм Ям з~) и входную цепочку ш длины л. Определение. Поверхностной конфигурацией (для краткости конфигурацией) автомата Р называют такую тройку (з, (, А), что з Е Я, ( — положение входной головки, 0«(а+1, и А — один из магазинных символов из т 0 (г.). Заметим, что конфигурация является МО, но не всякое МО является конфигурацией.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
