Глава 3 Контекстно-свободные языки
3.1 Свойства и распознаватели КС-языков
3.1.1
Автоматы с магазинной памятью
– распознаватели КС-языков
Распознаватели, определяющие КС-языки, моделируются автоматами с магазинной памятью (МПА). Дадим строгое определение такого автомата.
Автомат с магазинной памятью (МПА) – это семерка P=(Q,V,Z,d,q0,z0,F), где
§ Q – множество состояний УУ автомата;
§ V – конечный входной алфавит (множество допустимых символов);
§ Z – специальный конечный алфавит магазинных символов автомата (обычно в него входят терминальные и нетерминальные символы грамматики, но могут использоваться и другие символы), VÍZ;
§ d – функция переходов, отображающая множество Q´(VÈ{l})´Z на конечное множество подмножеств множества (Q´Z*);
§ q0 – начальное состояние автомата: q0ÎQ;
§ z0 – начальный символ магазина: z0ÎZ;
§ F – множество конечных состояний автомата: FÍQ, F¹Æ.
В отличие от конечного автомата (КА), рассмотренного в предыдущей главе, МП-автомат имеет «стек» магазинных символов, который играет роль дополнительной, или внешней памяти. Переход МПА из одного состояния в другое зависит не только от входного символа и текущего состояния, но и от содержимого стека. Таким образом, конфигурация МПА определяется уже тремя параметрами: состоянием автомата, текущим символом входной цепочки и содержимым стека.
Итак, конфигурация, или мгновенное описание (МО) МПА – это тройка (q,w,a)ÎQ´V*´Z*, где q – текущее состояние УУ, w – непрочитанная часть входной цепочки, a – содержимое магазина. Если w=l, считается, что цепочка прочитана; если a=l, то магазин считается пустым.
Начальная конфигурация МПА определяется как (q0,w,z0), wÎV*. Множество конечных конфигураций – как (q,l,z), где qÎF, zÎZ*.
Такт работы МП-автомата будем обозначать отношением ├─ на множестве конфигураций и описывать в виде (q,aw,ta)├─ (q¢,w,ga), если (q¢,g)Îd(q,a,t), где q,q¢ÎQ, aÎVÈ{l}, wÎV*, tÎZ, g,a ÎZ*. При выполнении такта автомат, находясь в состоянии q, считывает символ входной цепочки ‘a’ и сдвигает входную головку на одну ячейку вправо, а из магазина удаляет верхний символ, соответствующий условию перехода, и заменяет цепочкой согласно правилу перехода. Первый символ цепочки становится вершиной стека. Состояние автомата изменяется на q¢. Допускаются переходы, при которых считывающая головка не сдвигается и входной символ игнорируется, тогда он становится входным символом при следующем такте, но состояние УУ и содержимое стека может измениться. Такие переходы называются l–тактами. Автомат может проделывать l–такты, когда уже прочёл входную цепочку или же в процессе её прочтения; но, если магазин пуст, следующий такт невозможен.
Итак, находясь в состоянии q и наблюдая символ входной ленты x, МПА на одном такте работы может проделать со стеком в зависимости от правил перехода одно из следующих действий:
1) Дописать в стек c верхним символом a символ x: d(q,x,a)={(q,xa)}. В общем случае может быть дописан другой символ, отличный от прочитанного.
2) Удалить из стека верхний символ a: d(q,x,a)={(q,l)}.
3) Оставить содержимое стека без изменений: d(q,x,a)={(q,a)}.
МПА допускает цепочку символов w, если, получив эту цепочку на вход, он может перейти в одну из конечных конфигураций, когда по окончании цепочки автомат находится в одном из конечных состояний: (q0,w,z0)├─*(q,l,z), где qÎF, zÎZ*. После окончания цепочки автомат может проделать некоторое количество l–тактов.
Язык, определяемый МП-автоматом P – это множество всех цепочек символов, допускаемых этим автоматом: L(P). Два автомата P1 и P2 эквивалентны, если они определяют один и тот же язык: L(P1)=L(P2).
Говорят, что МПА допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из своих конечных состояний, а стек пуст, т.е. получена конфигурация (q,l,l), qÎF. Язык, заданный автоматом P, допускающим цепочки с опустошением стека, обозначается как Ll (P). Для любого МП-автомата всегда можно построить эквивалентный ему МПА, допускающий цепочки с опустошением стека: " МПА P $ МПА P¢ ½ L(P)=Ll (P¢).
Кроме обычного МПА, существует понятие расширенного МПА. Расширенный МПА может заменять не один символ в вершине стека, а цепочку символов конечной длины, на некоторую другую цепочку символов. Для любого расширенного МПА всегда можно построить эквивалентный ему обычный МП-автомат. Следовательно, классы МПА и расширенных МПА эквивалентны.
Пример. Построим МПА с опустошением стека, определяющий язык L={0n1n½n³0} – множество цепочек, в которых сначала подряд стоит некоторое количество нулей, а затем так же подряд столько же единиц.
Работа данного МП-автомата P должна состоять в том, что он копирует в магазин начальную часть входной цепочки, состоящую из нулей, а затем (как только на входе начнут появляться единицы) устраняет из магазина по одному нулю на каждую прочитанную единицу. Если нули в магазине и единицы на входе закончились одновременно, это означает, что их количества равны. Заметим, что в общем случае символы магазина могут отличаться от символов входной цепочки – например, на каждый прочитанный на входе 0 в магазин может записываться символ ‘a’. Построим этот МПА.
P=({q0,q1},{0,1},{Z,0},d,q0,Z,{q0}), где функция переходов имеет вид:
|
d(q0,0,Z)={(q0,0Z)} |
d(q0,1,0)={(q1,l)} |
d(q0,l,Z)={(q0,l)} |
|
d(q0,0,0)={(q0,00)} |
d(q1,1,0)={(q1,l)} |
d(q1,l,Z)={(q0,l)} |
Следует отметить, что при появлении во входной цепочке первой единицы после последовательности нулей состояние МПА должно измениться для того чтобы исключить возможность прочтения нулей вперемешку с единицами. Т.е. одно состояние – то, в котором читаются все нули и записываются в стек (q0), другое (q1)– при котором эти нули из стека удаляются.
Пусть входная цепочка имеет вид w=’0011’. Тогда смена конфигураций выглядит следующим образом:
(q0,0011,Z)├─(q0,011,0Z)├─(q0,11,00Z)├─(q1,1,0Z)├─(q1,l,Z)├─(q0,l,l). Цепочка допущена заданным автоматом.
Утверждение
1. Для произвольной КС-грамматики всегда можно построить МП-автомат, распознающий задаваемый этой грамматикой язык.
2. Для произвольного МП-автомата всегда можно построить КС-грамматику, которая будет задавать язык, распознаваемый этим автоматом.
МПА называется недетерминированным, если из одной и той же его конфигурации возможен более чем один следующий переход.
МПА называется детерминированным, если из любой его конфигурации возможно не более одного следующего такта. Класс ДМП-автоматов и соответствующих языков заметно уже, чем весь класс КС-языков и соответственно, МП-автоматов. В отличие от КА, не для каждого МПА возможно построить эквивалентный ему ДМП-автомат.
ДМП-автоматы определяют особый подкласс среди КС-языков, называемый детерминированными КС-языками. Все языки, относящиеся к этому классу, могут быть построены с помощью однозначных КС-грамматик, следовательно, они играют особую роль в теории языков программирования. Поэтому ДМПА необходимы при создании компиляторов. На основе ДМПА может быть построен синтаксический распознаватель любого языка программирования.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
