Магазинные (снековые) автоматы

Лекция. МАГАЗИННЫЕ (СТЕКОВЫЕ) АВТОМАТЫ Описание контекстно-свободных языков посредством контекстносвободных грамматик, по существу, эквивалентно использованию нотации Бэкуса-Наура при определении синтаксиса ряда языков программирования. С другой стороны, естественен вопрос о существовании класса моделей автоматов, отвечающих классу КС-языков. Например, уже такой язык L как L = {anbn | n 0}, не распознается конечным автоматом в смысле определения лекции. На уровне эвристического обсуждения это происходит оттого, что конечные автоматы имеют только конечную память, хотя распознавание контекстно-свободного языка может потребовать запоминания неограниченного объема информации. Скажем при считывании строки из языка L = {anbn | n 0}, следует не только проверить, что все символы а предшествуют первому вхождению символа b, но также требуется «запоминать» количество вхождений символа а. В силу произвольности числа n, этот подсчет вряд ли возможен, если располагать лишь конечной памятью. Видимо потребуется модель устройства, которая не содержит такого ограничения. Кроме того, для некоторых языков, таких, как язык { - R }, требуется выполнение действий, дающих возможность большую, чем просто способность к неограниченному счету. Важна способность запоминать и сравнивать последовательность символов в прямом и обратном порядках. В информатике модель такого вида используется под названием магазин (или стек). Это приводит к рассмотрению класса моделей, называемых магазинными или стековыми автоматами. Оказывается, эта идея приводит к довольно адекватной модели распознавателя для классов КС-языков. Данная лекция посвящена анализу соотношения между магазинными автоматами и контекстно-свободными языками. Будет показано, что в недетерминированном варианте класс таких стековых автоматов распознает именно семейство КС-языков. Тем не менее, на этом аналогия с детерминированными и недетерминированными моделями конечных автоматов обрывается: класс детерминированных магазинных автоматов определяет класс языков, отличных от всего семейства КС-языков. Выделяется подкласс так называемых детерминированных КС-языков, образующих собственное подмножество множества всех КС-языков. Этот класс языков и моделей автоматов оказывается интересным с прикладной точки зрения: разработка эффективных методов трансляции языков программирования опирается на эту модель вместе с использованием ДКА. Удобно начать обсуждение в рамках недетерминированной модели. Недетерминированные магазинные автоматы Опишем кратко эвристику модели. Схематически магазинный автомат можно представить в наглядных терминах следуя изображению на рис. 12.1. На каждом шаге работы устройство управления считывает один символ с входной ленты, меняет внутреннее состояние, и одновременно изменяет содержимое магазина посредством известных из элементарного программирования стековых операций. Рис. 12.1. Магазинный автомат Каждый следующий такт работы, совершаемый устройством управления, определяется прочитанным символом входной ленты, верхним символом стека и внутренним состоянием автомата. Результатом такого такта работы будет как новое состояние устройства управления, так и замена содержимого вершины стека. Если ограничиться рассмотрением лишь автоматов-распознавателей, то формальное определение модели выглядит следующим образом. Определение 12.1. Недетерминированный магазинный автомат (НМА) определяется как семерка M = (Q, , V, , q0, z0, F), где: Q = {q0, q1, ...,qn} – конечное множество внутренних состояний автомата; – конечное множество символов, называемых входным алфавитом; V – конечное множество символов, называемое стековым алфавитом;  – функция переходов автомата, определяемая отображением : Q ( { }) V {S | S – конечное подмножество множества Q V*}; q0 – начальное состояние автомата, q0 Q; z0 – начальный символ стека, z0 V; F – множество заключительных (или финальных) состояний автомата, F Q. Функция  зависит от трех аргументов (q, a, z), причем q обозначает состояние автомата в данный момент, а – обозреваемый входной символ и z – символ на вершине стека. Значениями (q, a, z) служит конечное множество пар (qi, i), где qi – следующее состояние автомата, а i – строка, помещаемая в вершину стека вместо символа z. Обратим внимание, что значением второго аргумента у функции  может быть символ пустой строки . Это означает, что возможен такт работы автомата, при котором ни один из входных символов не читается. Такой такт называется -переходом. Что касается третьего аргумента, то его значение не может быть пустым словом Иначе говоря, такт работы невозможен, если стек пуст. Тем не менее, имеются и другие интерпретации, связанные с функцией переходов стекового автомата. Пример 12.2. Пусть среди множества правил перехода НМА имеется правило (q1, a, b) = {( q2, cd), (q3, )}. Тогда, если на некотором такте работы автомат, находясь в состоянии q1, читает входной символ а и при этом имеет в вершине стека символ b, то возможно одно из двух: - автомат переходит в состояние q2, и строка cd заменяет символ на вершине стека (при этом в вершине стека оказывается символ с); - автомат переходит в состояние q3, при этом символ b удаляется из вершины стека. Пример 12.3. Рассмотрим НМА со следующим описанием: Q = {q0, q1, q2, q3}, = {a, b}, V = {0, 1}, z0 = 0, F = {q3}, а функция  задается соотношениями: (q0, a, 0) = {(q1, 10), (q3, )}, q0, , 0) = {(q3, )}, (q1, a, 1) = {(q1, 11)}, (q1, b, 1) = {(q2, )}, (q2, b, 1) = {(q2, )}, (q2, , 0) = {(q3, )}. Из этого описания видно, что функция  не всюду определена. Скажем, для (q0, b, 0) соотношение, указывающее значения , отсутствует. В таком случае интерпретируем значение функции  как пустое множество, из которого нет переходов в другое состояние. Основными соотношениями для функции  являются следующие два: первое - (q1, a, 1) = {(q1, 11)}, которое добавляет 1 в стек, при прочтении очередного символа а, и второе - (q2, b, 1) = {(q2, )}, которое удаляет 1 из стека, если во входной строке встречается символ b. Указанные два такта работы подсчитывают число символов а во входном слове и сравнивают с числом символов b в нем же. Автомат находится в состоянии q1 до тех пор, пока не встретит на ленте первое вхождение символа b. После чего он переходит в состояние q2. Это гарантирует распознавание того, что ни один символ b не встретится раньше самого последнего символа а. Анализ остальных соотношений для функции  показывает, что автомат переходит в состояние q3 тогда и только тогда, когда входная строка имеет следующий вид: anbn или а. Другими словами, входная строка принадлежит языку L = {anbn | n 0} {a}. Как и в ситуации с конечными автоматами-распознавателями говорят, что НМА распознает или допускает язык L. Возвращаясь к общему определению НМА, введем понятие конфигурации. Если q1 – текущее состояние НМА, a – непрочитанная часть входной строки, b – содержимое стека с символом b в его вершине, то упорядоченную тройку (q1, a , b ) назовем конфигурацией магазинного автомата. Преобразование одной конфигурации в другую с помощью одного такта работы автомата обозначается специальным символом . Говорят, что переход: (q1, a , b ) (q2, , ) возможен тогда и только тогда, когда (q2, ) (q1, a, b). Последовательности переходов, состоящие из произвольного числа тактов, обозначим посредством символов один шаг действительно имеет (или место). для случая, когда хотя бы Идентификацию переходов, совершаемых заданным автоматом М, будем обозначать символом M с нижним индексом М. Определение 12.4. Если М = (Q, , V, , q0, z0, F) – недетерминированный магазинный автомат, то язык, распознаваемый автоматом М, – это следующее множество входных слов: * и (q0, , z0) L(M) = { | M (qf, , ), qf F, V*}. Тем самым, язык, распознаваемый НМА М, это множество строк в алфавите , которые переводят автомат М из начального состояния в финальное состояние после прочтения входной строки (при этом содержимое стека не играет никакой роли и может быть любым). Пример 12.5. Построить НМА для языка {a, b}* и | |a = | |b}, L={ | где | |a и | |b суть числа вхождений символов а и b в строку . Оставляя пока в стороне то, какие соображения лежали в основе построения, возьмём в качестве примера автомата НМА со следующим описанием M = ({q0, qf), {a, b}, {0, 1, z}, , q0, z, {qf}), где  определяется соотношениями: (qo, , z) = {(qf, z)}, (qo, a, z) = {(q0, 0z)}, (qo, b, z) = {(q0, 1z)}, (qo, a, 0) = {(q0, 00)}, (qo, b, 0) = {(q0, )}, (qo, a, 1) = {(q0, )}, (qo, b, 1) = {(q0, 11)}. Этот НМА действительно распознает взятый язык L слов с равным числом вхождений символов а и b. В частности, при чтении строки baab НМА М проделает следующие такты работы: (qo, baab, z) (qo, aab, 1z) (qo, ab, z) (qo, b, 0z) (qo, , z) (qf, , z). Следовательно, эта строка распознается автоматом М. Пример 12.6. Построить НМА, допускающий язык R L={ При построении {a, b}+}. | недетерминированного магазинного автомата, распознающего данный язык, воспользуемся тем фактом, что символы извлекаются из стека в порядке, обратном тому, в котором они туда заносились. Поэтому при чтении первой половины входной строки автомат отправляет последовательно читаемые символы в стек, а при чтении второй половины строки сравнивает текущий входной символ с тем символом, который находится на вершине стека, до тех пор, пока не закончатся символы входной строки. В силу того, что символы извлекаются из стека в порядке, обратном тому, в котором они заносились в стек, то полностью сканирование входного слова окажется успешным тогда и только тогда, когда входная строка имеет вид R для произвольной строки {a, b}+. Важным моментом здесь является то, что заранее неизвестно, где находится середина входной строки, т.е. существенно выделение префикса и суффикса R . Преодолеть эту трудность может помочь недетерминированный характер строящегося автомата: НМА правильно указывает, где находится середина входного слова, и фиксирует это своими состояниями. Теперь будем, строить НМА М = (Q, , V, , q0, z0, F), где Q = {q0, q1, q2}, = {a, b}, V = {a, b, z}, F = {q2}, применяя изложенные выше соображения. Соотношения, определяющие функцию , разбиваем на несколько групп команд: а) команды, заносящие слово (qo, а, a) = {(q0, aa)}, (qo, b, a) = {(q0, ba)}, (qo, a, b) = {(q0, ab)}, в стек: (qo, b, b) = {(q0, bb)}, (qo, a, z) = {(q0, az)}, (qo, b, z) = {(q0, bz)}, b) команды, определяющие середину входной строки, за счет переходов из состояния q0 в q1: (qo, , a) = {(q1, a)}, (qo, , b) = {(q1, b)}, c) команды, сравнивающие реверсное слово R с содержимым стека: (q1, а, a) = {( q1, )}, (q1, b, b) = {(q1, )}, (q1, , z) = {(q2, z}. С целью тестовой проверки работы описанной программы M рассмотрим последовательность тактов при распознавании этим автоматом входной строки abba: (qo, abba, z) (qo, bba, az) (q1, ba, baz) (q1, a, az) (qo, ba, baz) (q1, , z) (q2, , z). Недетерминированный выбор при определении середины входной строки возникает на третьем такте. На этом такте работы НМА имеет конфигурацию (q0, ba, baz) и имеются две возможности для следующего такта: один из них использует команду (qo, b, b) = {(q0, bb)} и порождает переход (q0, ba, baz) (q0, a, bbaz), а другой – порождается использованной выше командой (qo, , b) = {(q1, b)}. Только выполнение этого такта приводит к распознаванию входной строки. Лекция 12. МАГАЗИННЫЕ (СТЕКОВЫЕ) АВТОМАТЫ Описание контекстно-свободных языков посредством контекстносвободных грамматик, по существу, эквивалентно использованию нотации Бэкуса-Наура при определении синтаксиса ряда языков программирования. С другой стороны, естественен вопрос о существовании класса моделей автоматов, отвечающих классу КС-языков. Например, уже такой язык L как L = {anbn | n 0}, не распознается конечным автоматом в смысле определения лекции. На уровне эвристического обсуждения это происходит оттого, что конечные автоматы имеют только конечную память, хотя распознавание контекстно-свободного языка может потребовать запоминания неограниченного объема информации. Скажем при считывании строки из языка L = {anbn | n 0}, следует не только проверить, что все символы а предшествуют первому вхождению символа b, но также требуется «запоминать» количество вхождений символа а. В силу произвольности числа n, этот подсчет вряд ли возможен, если располагать лишь конечной памятью. Видимо потребуется модель устройства, которая не содержит такого ограничения. Кроме того, для некоторых языков, таких, как язык { - R }, требуется выполнение действий, дающих возможность большую, чем просто способность к неограниченному счету. Важна способность запоминать и сравнивать последовательность символов в прямом и обратном порядках. В информатике модель такого вида используется под названием магазин (или стек). Это приводит к рассмотрению класса моделей, называемых магазинными или стековыми автоматами. Оказывается, эта идея приводит к довольно адекватной модели распознавателя для классов КС-языков. Данная лекция посвящена анализу соотношения между магазинными автоматами и контекстно-свободными языками. Будет показано, что в недетерминированном варианте класс таких стековых автоматов распознает именно семейство КС-языков. Тем не менее, на этом аналогия с детерминированными и недетерминированными моделями конечных автоматов обрывается: класс детерминированных магазинных автоматов определяет класс языков, отличных от всего семейства КС-языков. Выделяется подкласс так называемых детерминированных КС-языков, образующих собственное подмножество множества всех КС-языков. Этот класс языков и моделей автоматов оказывается интересным с прикладной точки зрения: разработка эффективных методов трансляции языков программирования опирается на эту модель вместе с использованием ДКА. Удобно начать обсуждение в рамках недетерминированной модели. Недетерминированные магазинные автоматы Опишем кратко эвристику модели. Схематически магазинный автомат можно представить в наглядных терминах следуя изображению на рис. 12.1. На каждом шаге работы устройство управления считывает один символ с входной ленты, меняет внутреннее состояние, и одновременно изменяет содержимое магазина посредством известных из элементарного программирования стековых операций. Рис. 12.1. Магазинный автомат Каждый следующий такт работы, совершаемый устройством управления, определяется прочитанным символом входной ленты, верхним символом стека и внутренним состоянием автомата. Результатом такого такта работы будет как новое состояние устройства управления, так и замена содержимого вершины стека. Если ограничиться рассмотрением лишь автоматов-распознавателей, то формальное определение модели выглядит следующим образом. Определение 12.1. Недетерминированный магазинный автомат (НМА) определяется как семерка M = (Q, , V, , q0, z0, F), где: Q = {q0, q1, ...,qn} – конечное множество внутренних состояний автомата; – конечное множество символов, называемых входным алфавитом; V – конечное множество символов, называемое стековым алфавитом;  – функция переходов автомата, определяемая отображением : Q ( { }) V {S | S – конечное подмножество множества Q V*}; q0 – начальное состояние автомата, q0 Q; z0 – начальный символ стека, z0 V; F – множество заключительных (или финальных) состояний автомата, F Q. Функция  зависит от трех аргументов (q, a, z), причем q обозначает состояние автомата в данный момент, а – обозреваемый входной символ и z – символ на вершине стека. Значениями (q, a, z) служит конечное множество пар (qi, i), где qi – следующее состояние автомата, а i – строка, помещаемая в вершину стека вместо символа z. Обратим внимание, что значением второго аргумента у функции  может быть символ пустой строки . Это означает, что возможен такт работы автомата, при котором ни один из входных символов не читается. Такой такт называется -переходом. Что касается третьего аргумента, то его значение не может быть пустым словом Иначе говоря, такт работы невозможен, если стек пуст. Тем не менее, имеются и другие интерпретации, связанные с функцией переходов стекового автомата. Пример 12.2. Пусть среди множества правил перехода НМА имеется правило (q1, a, b) = {( q2, cd), (q3, )}. Тогда, если на некотором такте работы автомат, находясь в состоянии q1, читает входной символ а и при этом имеет в вершине стека символ b, то возможно одно из двух: - автомат переходит в состояние q2, и строка cd заменяет символ на вершине стека (при этом в вершине стека оказывается символ с); - автомат переходит в состояние q3, при этом символ b удаляется из вершины стека. Пример 12.3. Рассмотрим НМА со следующим описанием: Q = {q0, q1, q2, q3}, = {a, b}, V = {0, 1}, z0 = 0, F = {q3}, а функция  задается соотношениями: (q0, a, 0) = {(q1, 10), (q3, )}, q0, , 0) = {(q3, )}, (q1, a, 1) = {(q1, 11)}, (q1, b, 1) = {(q2, )}, (q2, b, 1) = {(q2, )}, (q2, , 0) = {(q3, )}. Из этого описания видно, что функция  не всюду определена. Скажем, для (q0, b, 0) соотношение, указывающее значения , отсутствует. В таком случае интерпретируем значение функции  как пустое множество, из которого нет переходов в другое состояние. Основными соотношениями для функции  являются следующие два: первое - (q1, a, 1) = {(q1, 11)}, которое добавляет 1 в стек, при прочтении очередного символа а, и второе - (q2, b, 1) = {(q2, )}, которое удаляет 1 из стека, если во входной строке встречается символ b. Указанные два такта работы подсчитывают число символов а во входном слове и сравнивают с числом символов b в нем же. Автомат находится в состоянии q1 до тех пор, пока не встретит на ленте первое вхождение символа b. После чего он переходит в состояние q2. Это гарантирует распознавание того, что ни один символ b не встретится раньше самого последнего символа а. Анализ остальных соотношений для функции  показывает, что автомат переходит в состояние q3 тогда и только тогда, когда входная строка имеет следующий вид: anbn или а. Другими словами, входная строка принадлежит языку L = {anbn | n 0} {a}. Как и в ситуации с конечными автоматами-распознавателями говорят, что НМА распознает или допускает язык L. Возвращаясь к общему определению НМА, введем понятие конфигурации. Если q1 – текущее состояние НМА, a – непрочитанная часть входной строки, b – содержимое стека с символом b в его вершине, то упорядоченную тройку (q1, a , b ) назовем конфигурацией магазинного автомата. Преобразование одной конфигурации в другую с помощью одного такта работы автомата обозначается специальным символом . Говорят, что переход: (q1, a , b ) (q2, , ) возможен тогда и только тогда, когда (q2, ) (q1, a, b). Последовательности переходов, состоящие из произвольного числа тактов, обозначим посредством символов один шаг действительно имеет (или место). для случая, когда хотя бы Идентификацию переходов, совершаемых заданным автоматом М, будем обозначать символом M с нижним индексом М. Определение 12.4. Если М = (Q, , V, , q0, z0, F) – недетерминированный магазинный автомат, то язык, распознаваемый автоматом М, – это следующее множество входных слов: * и (q0, , z0) L(M) = { | M (qf, , ), qf F, V*}. Тем самым, язык, распознаваемый НМА М, это множество строк в алфавите , которые переводят автомат М из начального состояния в финальное состояние после прочтения входной строки (при этом содержимое стека не играет никакой роли и может быть любым). Пример 12.5. Построить НМА для языка {a, b}* и | |a = | |b}, L={ | где | |a и | |b суть числа вхождений символов а и b в строку . Оставляя пока в стороне то, какие соображения лежали в основе построения, возьмём в качестве примера автомата НМА со следующим описанием M = ({q0, qf), {a, b}, {0, 1, z}, , q0, z, {qf}), где  определяется соотношениями: (qo, , z) = {(qf, z)}, (qo, a, z) = {(q0, 0z)}, (qo, b, z) = {(q0, 1z)}, (qo, a, 0) = {(q0, 00)}, (qo, b, 0) = {(q0, )}, (qo, a, 1) = {(q0, )}, (qo, b, 1) = {(q0, 11)}. Этот НМА действительно распознает взятый язык L слов с равным числом вхождений символов а и b. В частности, при чтении строки baab НМА М проделает следующие такты работы: (qo, baab, z) (qo, aab, 1z) (qo, ab, z) (qo, b, 0z) (qo, , z) (qf, , z). Следовательно, эта строка распознается автоматом М. Пример 12.6. Построить НМА, допускающий язык R L={ При построении {a, b}+}. | недетерминированного магазинного автомата, распознающего данный язык, воспользуемся тем фактом, что символы извлекаются из стека в порядке, обратном тому, в котором они туда заносились. Поэтому при чтении первой половины входной строки автомат отправляет последовательно читаемые символы в стек, а при чтении второй половины строки сравнивает текущий входной символ с тем символом, который находится на вершине стека, до тех пор, пока не закончатся символы входной строки. В силу того, что символы извлекаются из стека в порядке, обратном тому, в котором они заносились в стек, то полностью сканирование входного слова окажется успешным тогда и только тогда, когда входная строка имеет вид R для произвольной строки {a, b}+. Важным моментом здесь является то, что заранее неизвестно, где находится середина входной строки, т.е. существенно выделение префикса и суффикса R . Преодолеть эту трудность может помочь недетерминированный характер строящегося автомата: НМА правильно указывает, где находится середина входного слова, и фиксирует это своими состояниями. Теперь будем, строить НМА М = (Q, , V, , q0, z0, F), где Q = {q0, q1, q2}, = {a, b}, V = {a, b, z}, F = {q2}, применяя изложенные выше соображения. Соотношения, определяющие функцию , разбиваем на несколько групп команд: а) команды, заносящие слово (qo, а, a) = {(q0, aa)}, (qo, b, a) = {(q0, ba)}, (qo, a, b) = {(q0, ab)}, в стек: (qo, b, b) = {(q0, bb)}, (qo, a, z) = {(q0, az)}, (qo, b, z) = {(q0, bz)}, b) команды, определяющие середину входной строки, за счет переходов из состояния q0 в q1: (qo, , a) = {(q1, a)}, (qo, , b) = {(q1, b)}, c) команды, сравнивающие реверсное слово R с содержимым стека: (q1, а, a) = {( q1, )}, (q1, b, b) = {(q1, )}, (q1, , z) = {(q2, z}. С целью тестовой проверки работы описанной программы M рассмотрим последовательность тактов при распознавании этим автоматом входной строки abba: (qo, abba, z) (qo, bba, az) (q1, ba, baz) (q1, a, az) (qo, ba, baz) (q1, , z) (q2, , z). Недетерминированный выбор при определении середины входной строки возникает на третьем такте. На этом такте работы НМА имеет конфигурацию (q0, ba, baz) и имеются две возможности для следующего такта: один из них использует команду (qo, b, b) = {(q0, bb)} и порождает переход (q0, ba, baz) (q0, a, bbaz), а другой – порождается использованной выше командой (qo, , b) = {(q1, b)}. Только выполнение этого такта приводит к распознаванию входной строки.