2.2. Формальные грамматики

Если вычислительная способность машины характеризуется сложностью языка, который она способна воспринимать, то нам нужен какой-то способ упорядочения языков по сложности. Мы опишем здесь способ, принадлежащий математику-лингвисту Хомскому (1963). Для понимания лингвистических представлений Хомского необходимо сначала усвоить его идею грамматики. Грамматика есть четверка , где — множество нетерминальных символов, или переменных, Т — множество терминальных символов, не пересекающееся с (в терминах предыдущих рассмотрений Т совпадает с множеством входных символов), объединение называют словарем грамматики Далее, — выделенный символ в множестве нетерминалов, называемый начальным. Р — конечное множество продукций, или правил переписывания. Каждая продукция имеет вид

где х и у — цепочки из V. Если продукция содержится в Р, то говорят, что цепочка у непосредственно выводима из х. Если продукции

содержатся в Р, то говорят, что цепочка выводима из х, и пишут должна быть хотя бы одна продукция вида и для каждого переменного символа должна быть продукция вида

где и у — (возможно, пустые) цепочки в V. Языком определяемым (порождаемым) грамматикой называют множество цепочек терминальных символов, выводимых из Таким образом, в предыдущем обозначении. Мы будем писать вместо в тех случаях, когда не должно возникнуть путаницы.

В качестве иллюстрации к идее множества продукций рассмотрим язык, определяемый словарем

и грамматикой

Этот язык содержит все цепочки, состоящие из цепочек х и следующих за ними цепочек у. Цепочку хххуу можно было бы получить так:

Правила типа (13) называются правилами непосредственно составляющих. Они всегда включают развертывание переменного символа в цепочку. Последовательное применение этих правил для получения цепочки терминальных символов можно продемонстрировать

на примере показателя структуры, представляющего собой диаграмму-дерево, которая показывает вывод каждого терминального символа из Такой показатель для (14) приведен на рис. 2,5. Если к грамматике добавить продукцию

то новая грамматика порождает качественно иной язык, поскольку эта продукция изменяет порядок символов в цепочке без развертывания нетерминального символа. Эта продукция называется трансформационной, и грамматики, которые содержат такие продукции, называются трансформационными.

Рис. 2.5. Показатель структуры для цепочки хххуу, порожденной грамматикой (13).

При применении трансформационной продукции надо различать отдельные вхождения одного и того же нетерминального символа. Например, пусть Т; обозначает член в простом арифметическом выражении. Коммутативность сложения можно выразить так:

но при этом надо указать, какой член засылается в какую ячейку.

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

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

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

Обычно грамматики разных видов иллюстрируются простым примером, чтобы лингвистические принципы были ясны. Для обоснования последующего обсуждения приведем два интересных, но более сложных примера. В табл. 2.1 описана грамматика, состоящая только из правил непосредственно составляющих. Это упрощение грамматики, принятой в Алголе 60 для определения простых арифметических выражений. Язык, порождаемый этой грамматикой, состоит из выражений типа

Таблица 2.1

Абстрактный язык на основе определения простых арифметических выражений в Алголе 60

(см. скан)

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

В табл. 2.2 перечислены правила преобразований. Если их вместе с алгебраическим правилом подстановки (любое простое арифметическое выражение может заменить свободную переменную) добавим к правилам табл. 2.1, получим язык для преобразования

Таблица 2.2. Язык для преобразования алгебраических выражений (см. скан)

арифметических выражений в эквивалентные. Допустим, что к рассматриваемому языку добавлены новый начальный символ и продукция

где — некоторое арифметическое выражение. Новый язык будет множеством цепочек, алгебраически эквивалентных цепочке Например, если заменить через в (11), то новый язык будет содержать цепочки

Основываясь на этом, рассмотрим задачу в пространстве состояний:

С помощью правил алгебры, данных в табл. 2.2, доказать, что эквивалентно

Эту задачу можно считать и лингвистической задачей распознавания, если в (18) заменить на

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

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

Язык типа 0, или язык без ограничений, порождается грамматикой, в которой все продукции имеют вид

где х и у — цепочки в V.

Язык типа 1, или контекстно-зависимый язык, порождается грамматикой, в которой все продукции имеют вид (19) и, кроме того, число символов в у не меньше числа символов в х. Значимость этого ограничения лучше всего оценить, анализируя продукцию, нарушающую его. Возьмем, например, правило из табл. 2.2. Можно показать (но мы этого делать не станем), что язык, порождаемый контекстно-зависимой грамматикой, может порождаться также грамматикой, в которой все продукции имеют вид

где w, х и у — цепочки в переменная (нетерминал). Продукцию (20) можно интерпретировать так:

Цепочка выводима из А, если А появляется в контексте х и у

Таким образом, (20) дает интуитивно более понятное определение контекстно-зависимой грамматики.

Язык типа 2, или контекстно-свободный язык, порождается грамматикой, в которой все продукции имеют вид

где, как и раньше, А — нетерминал, — цепочка в У.

Наконец, язык типа 3, или регулярный язык, порождается грамматикой, продукции которой имеют вид

или

где а — терминал, а В - нетерминал.

Легко видеть, что все языки типа 3 являются языками типа 2, языки типа 2 — языками типа 1, языки типа 1 — языками типа 0. Поэтому не удивительно, что только очень мощные автоматы способны воспринимать языки типа 0, несколько менее мощные — языки типа 1 и т. д.