Главная Промышленная автоматика.

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

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

реваемым входно!) головкой do

begin

удалить верхний символ из магазина; сдвинуть входную головку на одну клетку вправо end

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

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

(б) Символ в вершине магазина не совпадает с текущим входным символом. Поскольку цепочка у и магазинный список совпадали до сих пор, Р может восстановить магазинный список, сдвигая входную головку влево и переписывая вход в магазин, пока не встретит с. В этот момент в магазине автомата Р записана цепочка fljaj+i. . .a„Zo при некотором 1<1<п >). Если i=n, то Р останавливается в незаключительном состоянии. В противном случае Р удаляет из магазина и сдвигает входную головку вправо к первому символу цепочки у%. Затем Р возвращается к шагу 4, пытаясь установить, не является ли у префиксом цепочки flj+i. . .йп.

Мы видим, что Р распознает, является ли у подцепочкой цепочки x*=aiai. . .а„, вполне естественным способом. Р пытается по очереди идентифицировать у с префиксом цепочки atUi+i. . .а„ для t= - 1,2, . . ., п. Если это ему удается, он допускает вход. Если нет, отвергает. Заметим, что на эту процедуру Р может затратить 0(л;-It/I) шагов. □

Пример 9.12. Рассмотрим язык L={w\wQ {а, Ь, с}*, w=xy, где \х\2 и х=х} (т. е. W имеет префикс длины не менее 2, являющийся палиндромом). Здесь верхний индекс R обозначает обращение цепочки; например, {abb)=bba. Требование jc2 наложено потому, что всякая цепочка из {а, Ь, с}+ начинается с одного из тривиальных палиндромов а, b или с. Рассмотрим 2ДМА Р, который на данной входной цепочке aiCj. . Мп ведет себя следующим образом.

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

1) Когда мы попадаем в такую ситуацию первый раз, t=l, но впоследствии f будет возрастать каждый раз на 1.



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

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

реваемым входной головкой do

begin

удалить верхний символ из магазина; сдвинуть входную головку на одну клетку вправо end

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

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

(б) Символ в вершине магазина не совпадает с текущим входным символом. В этом случае Р сдвигает входную головку влево, переписывая вход в магазин, пока головка не достигнет левого концевого маркера. Если первоначальная входная цепочка имела вид flifla- • -Яп. то в этот момент в магазине автомата Р записано ai. . MiUiZo для некоторого i. Если i=2, то Р останавливается и отвергает вход. В противном случае Р удаляет из магазина и сдвигает входную головку на одну клетку вправо - к символу, стоящему непосредственно справа от левого концевого маркера. Затем Р возвращается к шагу 3.

Таким образом, Р устанавливает, начинается ли входная цепочка с палиндрома, пытаясь последовательно идентифицировать а. . . . . .fli с префиксом цепочки а. . .а„ для каждого i, 2in. На эту процедуру Р, возможно, затратит 0{п) шагов. □

Покажем, что за время 0{\w\) можно распознать, допускает ли 2ДМА Р входную цепочку w, независимо от того, сколько шагов в действительности делает Р. На протяжении последующего обсуждения мы считаем фиксированными 2ДМА P={S, I, Т, 6, So, Zo, Sf) и входную цепочку w длины п.

Определение. Поверхностной конфигурацией (для краткости конфигурацией) автомата Р называют такую тройку (s, i, А), что sS, i - положение входной головки, 0<г<п+1, и Л - один из магазинных символов из Г и {Zo}.

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



этой конфигурации. Говорят, что конфигурация C=(s, t". А) выводима из конфигурации C=(s, i, А), и пишут С =Ф С, если найдется такая последовательность шагов автомата Р, что при тО

где 0;>2 для каждого t *). В этой последовательности шагов промежуточные МО (s, i], aj) имеют в магазине не менее двух символов. Мы будем оперировать с конфигурациями, а не с МО, потому что конфигураций только 0(п), а число различных МО может быть экс поненциальным.

Определение. Конфигурацию (s, i. А) называют терминальной, если значение 6 (s, Aj, А) не определено или имеет вид (s, d, pop). Иными словами, терминальная конфигурация приводит или к остановке автомата Р, или к удалению символа из магазина. Терминатором конфигурации С называется такая единственная терминальная конфигурация С (если она существует), что С=Ф>* С, где =Ф* - рефлексивное и транзитивное замыкание отношения =».

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

Из рис. 9.17 видно, например, что в конфигурациях Со и Сц в вершине стека находится Zo. Поскольку между этими конфигурациями нет конфигурации с Zo в вершине стека, то Со Сц. Если Сц - заключительная конфигурация, то Сц служит терминатором как для себя, так и для Со. Из этого рисунка можно также вывести, что Ci Са, Ci=C, Ci=»* Сю и Сю - терминальная конфигурация, поскольку она приводит к тому, что Р удаляет символ из магазина. □

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

Лемма 9.1. Р допускает w тогда и только тогда, когда некоторая конфигурация вида (Sf, i, Zo), 0<1<ш+1, служит терминатором начальной конфигурации (so, 1, Zo).

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

1) Если т=0, го С [-С.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 [122] 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0037