Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

До сих пор мы рассматривали грамматики только с точки-зре­ ния содержательной интерпретации. Теперь остановимся на неко­ торых чисто формальных свойствах грамматик, т. е. на математи­ ческой теории порождающих грамматик, которая в настоящее вре­ мя довольно хорошо развита.

В теории грамматик часто возникают вопросы о наличии или отсутствии того или иного алгоритма, т. е. об алгоритмической раз­ решимости или неразрешимости проблем. Например:

1) существует ли алгоритм, позволяющий по любой данной КС-грамматике узнать, является ли порождаемый ею язык конеч­ ным (т. е. конечно ли порождаемое ею множество терминальных цепочек)? Аналогичный вопрос возникает относительно НС-грам­ матик;

2) существует ли алгоритм, позволяющий узнать относительно любой КС-грамматики, приписывает ли она каждой порождаемой терминальной цепочке только одну синтаксическую структуру, т. е. имеются ли терминальные цепочки, которые могут быть выведены в данной грамматике более чем одним способом?

Подобные вопросы и образуют круг алгоритмических проблем теории грамматик.

Представим некоторые результаты, относящиеся к проблемам разрешения для основных классов грамматик в виде табл. 3, где указано, для каких проблем доказана их разрешимость или нераз­ решимость.

Буква Р означает, что данная проблема разрешима, т. е. су­ ществует алгоритм, дающий ответ на вопрос. Буква Н означает, что проблема неразрешима. Знак ? соответствует тому, что неиз­ вестно, существует ли разрешающий алгоритм.

Как видно из таблицы, в классе КС-грамматик оказываются распознаваемыми некоторые из тех свойств, которые нераспоз­ наваемы в классе НС-грамматик (разумеется, свойства, распозна­ ваемые для НС-грамматик, распознаваемы и для КС-грамматик). К ним относятся:

а) свойство порождать пустой язык, состоящее в том, что суще­ ствует алгоритм, позволяющий для любой КС-грамматики узнать, порождает ли она хотя бы одну терминальную цепочку (п. I ) ;

б) свойство порождать конечный язык (п. 2); в) свойство порождать хотя бы одну цепочку, содержащую

вхождение данной цепочки ip. Это свойство означает, что по КС-грамматике для любого словосочетания можно определить, вхо­ дит ли оно хотя бы в одну фразу языка. Таким образом, в отличие

145

от НС-грамматик, где распознаваема правильность целых фраз, но не частей фраз, для КС-грамматик распознаваемо и то и другое (п. 10).

Т а б л и ц а 3

6Пусто ли пересечение языков, порождаемых двумя данными грамматиками

10Для любых ф и t|) выводимо ли слово, содер­ жащее г|) из ф в данной грамматике

Тем не менее многие важные свойства нераспознаваемы и для КС-грамматик. В частности, нераспознаваемы следующие свойст­ ва:

порождать полный язык (содержащий всевозможные цепочки, составленные из терминальных символов, п. 3);

иметь эквивалентную КС-грамматику, приписывающую каждой терминальной цепочке только одну синтаксическую структуру (п. 11);

эквивалентность произвольных двух грамматик, т. е. не суще­ ствует алгоритма, позволяющего по любой паре КС-грамматик уз­ нать, являются ли они эквивалентными (п. 12).

146

В классе Л-грамматик распознаваемы все свойства, перечислен­ ные в таблице.

Из проблем, относящихся к алгоритмам не для классов грам­ матик, а для конкретных фиксированных грамматик, мы рассмот­ рим только одну: так называемую проблему распознавания замещаемости. Она состоит в том, чтобы для данной грамматики G най­ ти алгоритм, позволяющий по любой паре цепочек\р> г|з узнать, за­ мещена ли ф на ф в языке L G . Для некоторых грамматик такие ал­ горитмы существуют, в частности, для всех А-грамматик. Однако имеются примеры КС-грамматик, для которых подобного алгорит­ ма нет.

Кроме алгоритмических проблем к математической теории грам­ матик относятся также проблемы оценки сложности вывода в грам­

«памяти». При этом под объемом памяти может пониматься, на­ пример, длина промежуточных цепочек, число вспомогательных символов в промежуточных цепочках, расстояние от первого вспо­ могательного символа до конца цепочки и т. д.

всех этих «времен» берется максимальное. Это и будет значением

Другими словами, хв{п) —это такое число шагов, которое, с од­ ной стороны, заведомо достаточно для вывода любой цепочки не длиннее п, а с другой стороны, необходимо. Условие необходимости вытекает из того, что среди выводимых цепочек не длиннее п имеет­ ся хотя бы одна цепочка, которую нельзя вывести меньше чем за Тс(«) шагов.

Исходя из понятия временной сигнализирующей функции, мож­ но получать оценки сложности вывода в разных грамматиках. Так,

147

Однако для КС-грамматик указанную оценку можно значитель­ но улучшить, т. е. понизить. Для любой КС-грамматики G b выпол­ няется неравенство %Gx (п) ^21п,

где / — число нетерминальных символов в Gt .

Эта оценка получается из следующих несложных соображений: любой КС-вывод можно провести так, чтобы на каждом шаге за­ менялся самый левый вспомогательный (нетерминальный) символ. Таким образом, на каждом шаге длина цепочки либо не изменяет­ ся, либо увеличивается, причем возможны шаги трех типов:

1.А—УВ («неудлиняющий нетерминальный»), где А я В нетер­ минальные символы;

2.А—уа («неудлиняющий терминальный), где А — нетерми­

няющих нетерминальных» шагов подряд. В самом деле, если бы

дут, т. е. получится «петля». Таким образом, в любом КС-выводе без «петель», а тем более в кратчайшем выводе не бывает более с— 1 неудлиняющих нетерминальных шагов подряд. Между двумя сериями таких шагов обязательно должен вклиниться хотя бы один шаг типа 2 или типа 3, а таких шагов всего не более 2п (не более

птерминальных, поскольку вся цепочка состоит из п терминальных символов, и не более п «удлиняющих», поскольку каждый удли­ няющий шаг увеличивает длину цепочки, а увеличиться более чем на

пэта длина не может). Стало быть, мы имеем не больше чем 2п

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

148