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

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

МП-автомат— это конечный автомат, снабженный дополнительным стеком (магазином) для хранения промежуточной информации потенциально беско­нечного объема (рис. 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.

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

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

• δ(s₀, ε, ┴) = (s, S┴) // в верхушке магазина помещаем начальный нетерми­нал грамматики G;
• (VαϵТ): δ(s, α, f(а)) = (s, ε) // если в верхушке магазина — символ f(а), со­ответствующий очередному входному терминалу а, то автомат переходит к следующему входному символу, выбрасывая из магазина верхний символ;
• (VAϵГ)(VA→αϵR): δ(s, ε, А) = (s, f(а)) // если в верхушке магазина стоит нетерминал, то МП-автомат, не читая очередного входного символа, заменяет его в магазине одной из альтернатив этого нетерминала из множества продукций грамматики G;
• δ(s, ε, ┴) = (q, ┴) // если в магазине больше нет символов, то переходим в заключительное состояние.

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

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

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

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

M_G5 = ({so, s, q), {(,)}, {S, (°,) °}, s₀,┴, δ, {q}).

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

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

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

δ (s,),)°) = (s, ε); // ------"-----------

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

δ (s, ε, S) = (s,(°S)⁰); // --------"----------;

δ (s, ε, S) = (s,ε); // --------"----------;

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

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

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

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

Поиск по сайту: