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

Управляющее устройство

Двусторонняя входная лента [томно читать)

Магазин

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

ПОЧКИ х). Тогда распознавание того, входит лну ъ х, эквивалентно распознаванию принадлежности цепочки хсу языку L. В этом разделе мы покажем, что существует 2ДМА, способный распознать L. Хотя этот 2ДМА может затратить 0{п) времени, но известна мощная техника моделирования, позволяющая промоделировать поведение данного 2Щ\к на входной цепочке длины п на РАМ, которая затратит на это 0(п) шагов. В настоящем разделе мы подробно изучим эту технику моделирования.

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

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



Управляющее устройство всегда находится в одном из состояний, принадлежащих конечному множеству S. Работа машины определяется функцией переходов 6, которая для всякого sgS, ag/U и {, $} и А Ти {Zo} указывает действие машины в случае, когда управляющее устройство находится в состоянии s, входная головка обозревает символ айв вершине магазина расположен символ Л. Возможны три типа действий машины:

(s, d, push В), где Вфг„

(s, d),

(s, d, pop), <сли Афг.

6(s, a, Л) =

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

Определение. Формально 2ДМА определяется как семерка P = (S, /, Т, 6, S., Zo, St),

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

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

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

4) 6 - отображение множества (S-{s,}) X (/ и {Ф, $}) х (Г и и {Zo}). Значение 6 (s, а. А), если определено, имеет один из следующих типов: (s, d, push В), is, d) или (s, d, pop), где sgS, BT HdG {-1. 0, -fl}. Мы считаем, что в заключительном состоянии Sf 2ДМА не делает никаких шагов, для некоторых других состояний шаги работы могут быть не определены. Кроме того, для любых s и Л во второй компоненте у 6(s, ф. А) не стоит d=-1, во второй компоненте у 6(s, $, А) не стоит d=+l. Наконец, в третьей компоненте у 6(s, а, Zo) не стоит pop.

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

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

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

Мгновенным описанием (МО) 2ДМА Р на входе w=aia2. . .Оп называется тройка (s, t, а), где

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

2) i - целое число, 0<t<rt+l, указывающее положение входной головки (считаем, что ао=ф и a„+i=$),

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



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

1) (S, i, Аа) \- is, i+d, ВАа), если 6(s, а,, A)={s, d, push S),

2) (s, i, Aa) h- (s. i+d, Aa), если 6(s, flj, Л)=(8, d),

3) (s, t, Ла) 1- (s, I+d, a), если 6(s, a,, Л)=(5, d, pop).

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

Начальное мгновенное описание 2ДМА Р для w=aiaa. . .а„ (без концевых маркеров) имеет вид (so, 1, Zo), показывающий, что Р находится в своем начальном состоянии Sq, входная головка обозревает самый левый символ из аа,. . .OnOn+i) и магазин содержит только нижний маркер Zo.

Допускающее мгновенное описание для w=ai. . .Оп имеет вид (S{, i, Zo) для некоторого Otn+l, показывающий, что автомат Р перешел в заключительное состояние Sf и магазин содержит только нижний маркер.

Говорят, что 2ДМА Р допускает входную цепочку w, если при входе W

(s„, 1, Zo)-(s,, i. Z.)

для некоторого 0ta;+l. Языком L{P), допускаемым автоматом Р, называется множество всех цепочек, допускаемых Р.

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

Пример 9.11. Рассмотрим язык {хсу \ х,у {а, Ь}* и у -

подцепочка цепочки х}. 2ДМА Р может распознать L следующим образом. Допустим, что автомату Р дана входная цепочка w вида хсу, где x=aiai. . .а„ и а, g {а, Ь), 1<1<л.

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

2. Р сдвигает свою входную головку влево, переписывая а„а„ 1. . Ml в магазин, пока входная головка не достигнет левого концевого маркера. В этот момент в магазине записано xZo=aia2. . . . . .a„Zo (самый левый символ цепочки xZt расположен в вершине магазина).

1) Если п=0, т. е. w=e, то Р обозревает o„+i=$, т. е. правый концевой маркер.





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