Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме

Страницы работы

55 страниц (Word-файл)

Содержание работы

Глава 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.  Для произвольного МП-автомата всегда можно построить КС-грамматику, которая будет задавать язык, распознаваемый этим автоматом.

МПА называется недетерминированным, если из одной и той же его конфигурации возможен более чем один следующий переход.

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

ДМП-автоматы определяют особый подкласс среди КС-языков, называемый детерминированными КС-языками. Все языки, относящиеся к этому классу, могут быть построены с помощью однозначных КС-грамматик, следовательно, они играют особую роль в теории языков программирования. Поэтому ДМПА необходимы при создании компиляторов. На основе ДМПА может быть построен синтаксический распознаватель любого языка программирования.

Похожие материалы

Информация о работе