Автоматы с магазинной памятью

2.6.2. Автоматы с магазинной памятью

Распознавателем КС-языков является класс автоматов с магазинной памятью (их называют также МПавтоматами). Мы рассмотрим МП-автоматы — распознаватели. МП-автоматы играют важную роль в теории языков— именно эти устройства и их модификации используются в большинстве практически работающих трансляторов для синтаксического анализа программ.

МП-автомат— это конечный автомат, снабженный дополнительным стеком (магазином) для хранения промежуточной информации потенциально бесконечного объема (рис. 2.17). МП-автомат имеет конечное множество внутренних состояний S с начальным состоянием s0 и подмножеством F заключительных состояний, конечный алфавит входных сигналов X и конечный алфавит магазина Г с маркером ┴, который обозначает дно стека. Функция переходов 8 по каждой тройке <текущее внутреннее состояние, очередной входной сигнал, верхний символ магазина> определяет на очередном шаге функционирования следующее состояние и цепочку символов магазинной памяти, записываемых в магазин вместо прочитанного верхнего символа (условимся, что цепочка записывается в стек "хвостом вперед", т. е. сначала в стек записывается последний символ цепочки, затем предпоследний и т. д.). МП-автомат распознает входную цепочку, если после ее завершения на входе автомат перейдет в одно из заключительных состояний и его магазин будет пустым.

ПРИМЕР 2.20. МП-автомат М= ({s}, {(,)},{A},s, ┴, δ , {s}) рис. 2.18 только

с одним состоянием распознает язык правильных скобочных выражений. Вначале стек пуст— в нем находится заключительный маркер _L. По каждой встретившейся на входе открывающей скобке ( автомат добавляет в магазин символ А (который отмечает, что соответствующая закрывающая скобка впоследствии должна встретиться во входной цепочке). Каждая встретившаяся на входе закрывающая скобка приводит к выбрасыванию символа А из магазина. Когда все символы и во входной строке, и в стеке исчерпываются, автомат остается в заключительном состоянии s.

Легко видеть, что любое нарушение структуры входной цепочки — несбалансированность скобок — не может привести к ситуации, когда при пустой входной строке стек автомата останется пустым.

МП-автомат является недетерминированным, если его функция переходов неоднозначна и/или в нем имеются s-переходы. Недетерминированный МПавтомат распознает входную цепочку, если существует последовательность шагов его работы, приводящая его из начального в одно из заключительных состояний после прочтения всей входной цепочки и пустом магазине.

Оказывается, что класс КС-языков совпадает с классом языков, распознаваемых недетерминированными МПавтоматами. Детерминированные МП-автоматы могут распознать лишь более узкий класс КС-языков, который все же более широк, чем класс автоматных языков. В частности, как мы видели, неавтоматный язык правильных скобочных выражений распознается простейшим детерминированным МП-автоматом (рис. 2.18).

Покажем, что по каждой КС-грамматике G = (T, N, S, R) можно построить (недетерминированный) МПавтомат МG ,распознающий язык, порождаемый G.

Множество состояний MG составляют три состояния: начальное s0, рабочее s и заключительное q. Множество входных сигналов искомого МП-автомата — это множество терминальных символов грамматики G. Алфавит магазина Г составляют все нетерминальные символы G и для каждого терминального символа αϵТ грамматики G в него входит символ α°, т. е. Г = NUТ°. Взаимнооднозначную функцию сопоставляющую каждому αϵТ элемент α°ϵТ°, обозначим f. Расширим определение функции f на множество N нетерминалов грамматики G, определяя ее на этом множестве как тождественную функцию. Далее будем считать, что эта функция на цепочках символов из TUN определяется покомпонентно.

Функция переходов δ искомого МП-автомата строится так:

δ(s0, ε, ┴) = (s, S┴) // в верхушке магазина помещаем начальный нетерминал грамматики G;

(VαϵТ) : δ(s, α, f(а)) = (s, ε) // если в верхушке магазина — символ f(а), соответствующий очередному входному терминалу а, то автомат переходит к следующему входному символу, выбрасывая из магазина верхний символ;

(VAϵГ)(VA→αϵR): δ(s, ε, А) = (s, f(а)) // если в верхушке магазина стоит нетерминал, то МП-автомат, не читая очередного входного символа, заменяет его в магазине одной из альтернатив этого нетерминала из множества продукций грамматики G;

δ(s, ε, ┴) = (q, ┴) // если в магазине больше нет символов, то переходим в заключительное состояние.

Легко видеть, что при удачном выборе последовательности выполнения команд построенный так МП-автомат (недетерминированно) моделирует процесс левостороннего порождения входной цепочки, если она является цепочкой языка, порождаемого грамматикой G.

ПРИМЕР 2.21. Построим МП-автомат MG5, распознающий язык правильных скобочных выражений, формально по двусмысленной грамматике G5: S→SS | (S) | ε, порождающей этот язык.

Множество состояний MG5 содержит начальное состояние s0, рабочее состояние s и заключительное состояние q. Множество его входных сигналов — множество терминалов грамматики G5. Магазинный алфавит включает символ S (единственный нетерминал грамматики) и пару символов,

(° и )°, соответствующих терминалам грамматики:

MG5 = ({so, s, q), {(,)}, {S, (°, ) °}, s0,┴, δ, {q}).

Функция переходов МП-автомата определится так:

δ(sо, ε, ┴) = (s, S┴); // в магазин записываем начальный нетерминал грамматики; автомат переходит в состояние s;

δ (s, (, (° ) = (s, ε); // если терминал входной цепочки и верхушка магазина совпадают, выбрасываем символ из магазина и переходим к следующему входному символу;

δ (s, ε, S) = (s, S S); //в соответствии с продукцией грамматики;

δ (s, ε, ┴) = (q, ┴); // при пустом магазине входная цепочка распознана, если она кончилась.

Алгоритм распознавания языка очень непросто построить по такому недетерминированному автомату.

Обратно, оказывается, что по каждому (недетерминированному) МП-распознавателю можно построить КСграмматику, порождающую распознаваемый этим автоматом язык. Это доказывается более сложно; доказательство можно найти, например, в [Г70].

Итак, МП-автомат может быть использован для представления любого языка типа 2. Очевидно также, что по любому МП-автомату может быть построена машина Тьюринга, моделирующая его функционирование.