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

Cz Ci-Ci Cf-Cs

2 Cr 77,9

Vacy70 aiaeoe

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

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

(1) C=(s, t, Л), D=( /, А),

(2) C=(s, В), D={t\ У, В),

(3) (S, t. Л) h (s, i, ВА),

(4) (/, у, ВА) h (, /, Л),

т. е. если Р может дойти из С в С с помощью шага push, а из D в D с помощью шага pop.

Лемма 9.2. Если (С, D) лежит ниже (С, D} и С D, то C=D.

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

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

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

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

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

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



смотренных конфигураций (С, D), для которых TEPM[C]=D. Список ВРЕМ нужен в процедуре КОРРЕКТИР(С, D), чтобы хранить предшественниц конфигурации С.

Мы поступаем следующим образом. Сначала полагаем ТЕРМ[С]= =С, если С - терминальная конфигурация. (Каждая терминальная конфигурация является своим терминатором.) Добавляем (С, С) к НОВ. Затем рассматриваем такие пары (С, D), что С- D за один шаг работы Р. (Заметим, что при таком шаге магазин не меняется.)

Если терминатор для D уже известен, полагаем ТЕРМ[£]= =TEPMID] для всех Е, о которых в этот момент известно, что они - предшественницы конфигурации С, включая саму С. (Собственные предшественницы находятся в ПРЕД[С1.) Добавляем также пару (Е, TEPM[D]) к списку НОВ.

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

В этот момент для каждой конфигурации С известна такая единственная конфигурация D, что С=ф*Ь без изменения магазина, и либо D - терминатор для С, либо D \- (s, i, а) при а=2. Теперь )ассматриваем все пары конфигураций, уже добавленные к списку -ЮВ. В общем случае НОВ содержит нерассмотренные пары конфигураций (А, В), в которых А =ф* В и В терминальна. Допустим, что НОВ содержит пару {А, В). Удаляем {А, В) из НОВ и рассматриваем все пары (С, D) конфигураций, лежащих ниже (А, В). Если терминатор для D уже вычислен, полагаем TEPM[C]=TEPM[D] и добавляем к списку НОВ пару (С, TEPMID]). Для каждой конфигурации Е из ПРЕД[С1 полагаем TEPM[£]=TEPM[D] и добавляем (Е, TEPM[D]) к списку НОВ. Но если терминатор для D еще не вычислен, помещаем С в список UPEJXlD]. Продолжаем эту процедуру, пока НОВ не опустеет. В этот момент найден терминатор (если он существует) для каждой конфигурации С.

Исчерпав весь список НОВ, рассматриваем TEPMlCol, где Со - начальная конфигурация. Если TEPMlCol - допускающая конфигурация, то 2ДМА Р допускает w. В противном случае Р отвергает ш.

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

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

Вход. 2ДМА P=(S, /, Т, б. So, Zo, Sf) и входная цепочка ш g /*,

\w\=n.

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

1. Произведем начальную загрузку массивов и списков следующим образом. Для каждой конфигурации С положим ТЕРМ[С1=0 и ПРЕД(С]=0. Положим НОВ=0 и ВРЕМ=0.



procedure КОРРЕКТИР(С, D): begin

comment Всякий раз, когда вызывается КОРРЕКТИР(С, D), имеем C=>D;

1. if TEPMfD] = 0 then добавить С к ПРЕДР] else

begin

2. ВРЕМ {С};

3. while ВРЕМ:5б0 do

begin

4. выбрать и удалить конфигурацию В из ВРЕМ;

5. ТЕРМ [В] ТЕРМ [D];

6. добавить (В, TEPM[D]) к НОВ;

7. for А е ПРЕД \В] do добавить А к ВРЕМ end

Рис. 9.18. Процедура КОРРЕКТИР.

2. Для каждой терминальной конфигурации С полагаем ТЕРМ[с1=С и добавляем к НОВ пару (С, С).

3. Для каждой конфигурации С проверяем, существует ли такая конфигурация D, что С\- D за один шаг. Если да, вызываем КОР-РЕКТИР(С, D). Процедура КОРРЕКТИР приведена на рис. 9.18.

4. Пока список НОВ не пуст, удаляем пару (С, D) из НОВ. Для каждой пары (С, D), лежащей ниже (С, D), вызываем КОР-РЕКТИР(С, D).

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

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

На шаге 2 обнаруживаем, что C, Се, Cj, Сю и Сц - терминальные конфигурации и потому свои же терминаторы. Добавляем к НОВ пары (Си С), (С, С), (С„ е.). (Сю, Сю) и (Сц, Сц).

На шаге 3 вызываем KOPPEKTHP(Ci, Сг). Поскольку в этот момент ТЕРМ[с2]=0, то КОРРЕКТИР всего лишь помещает Ci в список ПРЕД[с21. На шаге 3 вызываем также КОРРЕКТИР(Сб, Се). Так как ТЕРМ[Св]=Св, то КОРРЕКТИР полагает ТЕРМ[Св]=С.





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.004