КС-языки и магазинные автоматы

КС-ЯЗЫКИ И МАГАЗИННЫЕ АВТОМАТЫ Цель этой лекции установление взаимосвязи между магазинными автоматами и контекстно-свободными языками. Точнее говоря, будет показано, что каждый КС-язык распознается некоторым НМА, и обратно, любой язык, распознаваемый недетерминированным магазинным автоматом, Оказывается КС-языком. Начнем с того, что каждому КС-языку сопоставим распознающий его НМА. Основанием конструкции такого НМА служит соображение, состоящее в воспроизведении автоматом строк заданного КС-языка. Построение такого автомата опирается на теорему о том, что любой КС-язык порождается КС-грамматикой в нормальной форме Грейбах. По сути дела магазинный автомат будет реализовывать левый вывод слов, через запоминание символов правой части сентенциальных форм в его стеке. В то же время левая часть формы, состоящая из терминалов, совпадает с прочитанной частью входного слова. Работа НМА начинается с занесения в стек аксиомы КС-грамматики. Чтобы моделировать на автомате применение правила A a нужно поместить метасимвол A в вершину стека и одновременно терминал a - считать обрабатываемым входным терминалом. Затем метасимвол А удаляется с вершины стека и заменяется на подслово нетерминальных символов . Отсюда становится ясным, какими должны быть команды автомата, определяющие функцию переходов . Реализуем описанный сценарий на примере. Пример 13.1. Построить стековый автомат, для порожденного грамматикой с правилами S aSbb a. Сначала приведем грамматику к нормальной форме Грейбах: S aSA a, A bB, B b. КС-языка, Для строящегося стекового автомата зарезервируем три состояния {q0, q1, q2}, q0 - начальное, q2 - заключительное состояние. Вначале командой (q0, , z) = {(q1, Sz)} заносим в стек аксиому S грамматики. Правило S aSA моделируется автоматом путем извлечения S из стека и его заменой на SA, при чтении входного символа a. Аналогично правилу S a отвечает извлечение символа S из стека как результат чтения символа a входной строки. Оба эти правила представляются в НМА командой (q1, a, S) = {(q1, SA), (q1, )}. Поступая аналогичным образом, сопоставим остальным КС-правилам команды: (q1, b, A) = {(q1, B)}, (q1, b, B) = {(q1, )}. Появление на вершине стека начального символа дна стека z означает завершение вывода, и переход НМА в заключительное состояние: (q1, , z) = {(q2, )}. Теорема 13.2. Для любого контекстно-свободного языка L, не содержащего , эффективно строится такой НМА M , что L = L(M). Доказательство. Возьмем КС-грамматику в нормальной форме Грейбах G = (N, T, S, P), порождающую КС-язык L. Построим стековый автомат, моделирующий тактами работы левосторонний вывод в этой грамматике. Выберем такое описание автомата: M = ({q0, q1, qf}, T, N {z0}, , q0, z0, {qf}), где z0 N. Отсюда, видны элементы конструкции: входной алфавит автомата совпадает с множеством терминалов грамматики G, стековый алфавит содержит множество всех нетерминалов из G. Функция переходов  будет содержать команду  (q0, , z0) = {(q1, Sz0)}. (13.3) После первого такта работы автомата M стек будет содержать символ S. (Стековый символ дна z0 будет служить маркером окончания вывода.) Кроме того, к множеству команд будут следующим образом добавляться команды: правилу A (q1, ) a из P отвечает команда (q1, a, A). (13.4) В силу (13.4) НМА M читает входной символ a, удаляет A из стека и заменяет ее на . Эта серия команд позволяет НМА моделировать левые выводы в G. Наконец, следует добавить команду (q1, , z0) = {(qf, z0)}, (13.5) позволяющую перейти M в заключительное состояние. Описание функции  завершено и требуется установить, что M распознает строки L(G). С этой целью рассмотрим частичный левый вывод * S a1a2...anA1A2...Am a1a2...anbB1B2...BkA2...Am. С учетом построения команд M после прочтения строки a1a2...an в стеке окажется слово A1A2...Am. Выполнение следующего шага вывода в G реализуется правилом A1 bB1...Bk. Но конструкция автомата M такова, что M должен иметь команду, согласно которой (q1, B1...Bk) (q1, b, A1). Поэтому в стеке после прочтения части a1a2...anb входного слова должно оказаться слово B1...Bk A2...Am. * Далее, индукцией по длине вывода получаем, что если S (q1, , Sz0) (q1, , z0). С учетом (13.3) и (13.5), имеем: (q0, , z0) (q1, , Sz0) Следовательно, выполнено включение L(G) (q1, , z0) L(M). (qf, , z0). , то Докажем обратное включение L(M) Если L(G). L(M), то, по определению распознавания слов автоматом, имеем: (q0, , z0) (qf, , ). В силу построения команд переход из q0 в q1 возможен лишь единственным образом, как и для перехода из q1 в qf. По этой причине верно соотношение (q1, , Sz0) Положим (q1, , z0). = a1a2a3...an. Тогда при обработке слова (q1, a1a2a3...an, Sz0) (13.6) (q1, , z0) первый шаг совершается по правилу типа (13.4). Следовательно (q1, a1a2a3...an, Sz0) (q1, a2a3...an, 1z0). Последнее означает, что в грамматике G есть правило вида S Отсюда следует, что S Далее, положив a1 1. a1 1. 1 = A 2, находим (q1, a2a3...an, A 2z0) (q1, a3...an, Отсюда следует, что G должна содержать продукцию A 3 2z 0). a2 3. Поэтому * S a1a2 3 2. Тем самым на каждом такте работы автомата содержимое стека (исключая символ z0) совпадает с еще не замещенной терминалами частью сентенциальной формы. С учетом (13.6) получаем * S Следовательно, L(M) L(G), и теорема доказана. Пример 13.3. По грамматике S aA, A aABC bB a, a1a2...an. B b, C c построить НМА, распознающий язык L(G). Грамматика уже имеет нормальную форму Грейбах. Обратимся сразу к построению серии команд НМА: (q0, , z0) = {(q1, Sz0)}, (q1, , z0) = {(qf, z0)}, (q1, a, S) = {(q1, A)}, (q1, a, A) = {(q1, ABC), (q1, )}, (q1, b, A) = {(q1, B)}, (q1, b, B) = {(q1, )}, (q1, c, C) = {(q1, )}. Рассмотрим протокол вычислений автомата на тестовой строке aaabc: (q0, aaabc, z0) (q1, aaabc, Sz0) (q1, aabc, Az0) (q1, abc, ABCz0) (q1, bc, BCz0) (q1, , z0) (q1, c, Cz0) (qf, , z0). Этой последовательности тактов протокола отвечает вывод: S aA aaABC aaaBC aaabC aaabc. Теперь проведем доказательство обратного по отношению к теореме 13.2 утверждения. С этой целью нужно, по данному НМА, построить грамматику, моделирующую такты работы автомата. Содержательно это означает, что содержимое стека должно совпадать с той частью сентенциальной формы, которая состоит из нетерминальных символов, в то время как прочитанная часть входной строки должна быть терминальным префиксом сентенциальной формы. Ради краткости проведем доказательство в частном случае, когда НМА удовлетворяет следующим дополнительным условиям: 1. НМА имеет единственное финальное состояние, которое достигается тогда и только тогда, когда стек полностью пуст; 2. Все команды имеют вид: (qi, a, A) = {k1, k2 , ... , kn}, где для любого r = 1, 2, ..., n kr = (qj, ) (13.8) kr = (qj, BC). (13.9) или В силу наложенных ограничений, каждый такт работы автомата увеличивает или уменьшает содержимое стека ровно на 1 символ. Учитывая условия 1 и 2, построим КС-грамматику для языка, распознаваемого таким НМА. Как и ранее требуется, чтобы сентенциальная форма вывода отражала содержимое стека. Конфигурации автомата содержат символ внутреннего состояния, роль которого также надо отразить в записи сентенциальной формы. В качестве нетерминальных символов грамматики G примем записи вида (qi A qj), интерпретируя это следующим образом: * (qi A qj) тогда и только тогда, когда НМА стирает A в стеке, и в результате чтения входного слова переходит из состояния qi в состояние qj. "Стирание" означает, что A удаляется из стека и на его место ничего не записывается, т.е. на вершине стека оказывается символ, непосредственно находившийся под самым верхним символом A. На основе этой интерпретации, нетрудно видеть, что правила грамматики должны отвечать одному из двух типов команд. Так (13.8) влечет немедленное стирание A (в стеке), что влечет наличие в грамматике соответствующих правил: (qi A qj) a. Командам типа (13.9) отвечают правила вида (qi A qk) a (qj B qt) (qt C qk), где qk и qt могут быть любыми символами из Q. Это связано с тем, что для стирания A сначала А заменяется на BC в результате чтения a и изменение состояния qi на qj. Далее при последовательном переходе из qj в qt, стирается B, а затем при смене qt на qk, стирается из стека C. В качестве аксиомы грамматики берется запись (q0 z0 qf), где qf единственное заключительное состояние рассматриваемого НМА. Наконец, точным образом сформулируем нужную теорему. Теорема 13.4. Если язык L распознается некоторым НМА M, то L является КС-языком. Доказательство. Допустим что, язык распознается L недетерминированным стековым автоматом M = (Q, , V, , q0, z0, {qf}), удовлетворяющим указанным выше условиям 1 и 2. Построим для L грамматику G = (N, T, S, P), где T = , а N состоит из записей вида (qi A qj). Применяя описанную выше конструкцию, покажем, что получившаяся грамматика такова, что для всех qi, qj Q; A V; V*; , * из соотношения (qi, ,A ) (13.11) (qj, , ), следует выводимость * (qi A qj) , и верна обратная импликация. Проведем детальный разбор доказательства, как пример обоснования правильности программ в модели стековых автоматов. Начнем доказательство с проверки следующего факта: если НМА таков, что символ A и его последователи могут быть удалены из стека в результате чтения строки и перехода из состояния qi в qj, то может быть выведена из нетерминала (qi A qj) в грамматике G. Это так, поскольку грамматика G как раз и была построена с таким расчетом. Точнее, достаточно провести рассуждение индукцией по числу тактов работы НМА. Чтобы доказать обратное утверждение рассмотрим отдельный шаг вывода в G следующего вида: (qi A qk) a(qj B qt) (qt C qk). Используя соответствующую команду для НМА (qi, a, A) = {(qj, BC), ...)}, (13.12) видим, что символ A в результате чтения a может быть удален из стека, а BC занесено в него с изменением состояния НМА с qi на qj. Аналогично, правилу (qi A qj) (13.13) a, отвечает соответствующая команда (qi, a, A) = {(qj, )}, (13.14) по которой символ A может быть удален из стека. Становится ясным, что сентенциальные формы, выводимые из метасимвола (qi A qj), определяют последовательность возможных конфигураций НМА, которая отвечает (13.11). Важно отметить, что переход (qi A qj) a(qj B qt) (qt C qk) возможен для некоторых (qj B qt), (qt C qk), которым не отвечают переходы вида (13.12) или (13.14). Однако в этом случае, по меньшей мере, один из этих метасимволов будет несущественным и не влияет на состав языка, порождаемого грамматикой G. Разумеется, для всех сентенциальных форм, порождающих терминальные строки, приведенные рассуждения также справедливы. Обратим внимание, что применение полученного результата к последовательности (q0, , z0) (qf, , ), возможно тогда и только тогда, когда * (q0 z0 qf) . Следовательно, L(M) = L(G), и требуемое доказано. Пример 13.5. Обсудим НМА со следующими командами: (q0, a, z) = {(q0, Az)}, (q1, a, A) = {(q0, A)}, (q0, b, A) = {(q1, )}, (q1, , z) = {(q2, )}, где q0, как прежде, начальное состояние, а q2 – заключительное. Перед построением соответствующей грамматики G заметим, что заданный НМА удовлетворяет условию 1, но не удовлетворяет условию 2. Чтобы удовлетворить условию 2, введем новое дополнительное состояние q3 и предусмотрим промежуточный такт, на котором вначале удаляется А из стека, а затем вновь туда помещается уже на следующем такте. Иными словами организуем новую совокупность команд: (q0, a, z) = {(q0, Az)}, (q3, , z) = {(q0, Az)}, (q0, a, A) = {(q3, )}, (q0, b, A) = {(q1, )}, (q1, , z) = {(q2, )}. Последние три команды имеют вид (13.8). Значит им отвечают такие правила грамматики: (q0Aq3) a, (q0Aq1) b, (q1zq2) . По двум первым командам составим правила: (q0zq0) a(q0Aq0)(q0zq0) | a(q0Aq1)(q1zq0) | a(q0Aq2)(q2zq0) | a(q0Aq3)(q3zq0), (q0zq1) a(q0Aq0)(q0zq1) | a(q0Aq1)(q1zq1) | a(q0Aq2)(q2zq1) | a(q0Aq3)(q3zq1), (q0zq2) a(q0Aq0)(q0zq2) | a(q0Aq1)(q1zq2) | a(q0Aq2)(q2zq2) | a(q0Aq3)(q3zq2), (q0zq3) a(q0Aq0)(q0zq3) | a(q0Aq1)(q1zq3) | a(q0Aq2)(q2zq3) | a(q0Aq3)(q3zq3), (q3zq0) (q0Aq0)(q0zq0) | (q0Aq1)(q1zq0) | (q0Aq2)(q2zq0) | (q0Aq3)(q3zq0), (q3zq1) (q0Aq0)(q0zq1) | (q0Aq1)(q1zq1) | (q0Aq2)(q2zq1) | (q0Aq3)(q3zq1), (q3zq2) (q0Aq0)(q0zq2) | (q0Aq1)(q1zq2) | (q0Aq2)(q2zq2) | (q0Aq3)(q3zq2), (q3zq3) (q0Aq0)(q0zq3) | (q0Aq1)(q1zq3) | (q0Aq2)(q2zq3) | (q0Aq3)(q3zq3). Начальным символом (аксиомой) грамматики считаем (q0, z, q2). Для тестовой строки aab, которая распознается данным НМА получается серия конфигураций: (q0, aab, z) (q0, b, Az) (q0, ab, Az) (q1, , z) (q3, b, z) (q2, , ). Соответствующий вывод в грамматике G будет иметь такой вид: (q0zq2) a(q0Aq3)(q3zq2) aab(q1zq2) aab. aa(q3zq2) aa(q0Aq1)(q1zq2)