Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
где f, g, h, ... суть многочлены, все коэффициенты которых равны 1.
Предложенный выше метод годится для решения системы также и при новой интерпретации. Последовательные приближения
(So, «о, «о, ...), (Si, «ь »„...),..•
— это формальные ряды специального вида, а именно многочлены. По модулю п, где п — максимальная длина их членов, эти многочлены эквивалентны искомому решению, к которому они стремятся как к индуктивному пределу.
В качестве упражнения читатель может переписать в новых обозначениях примеры, которые мы рассматривали в предыдущем разделе.
Здесь мы приведем новый пример, который интересен и сам по себе.
Пример. Выше мы рассматривали неоднозначную грамматику с правилами
I S -+SaS, S-*b\.
Напротив, грамматика с правилами
I S -*¦ aSS, S-+b I,
соответствующая бесскобочной записи (тех же — в содержательном смысле — формул!), является однозначной. Следовательно, соответствующий ряд — характеристический (т. е. все его коэффициенты равны 0 и 1). Чтобы получить этот ряд, выпишем уравнение
2 = а22 + Ь,
решая которое, получаем S0 = 2, = 6,
2г = а{Ь){Ь) + Ь; Гл. XI. Задание языков с помощью систем уравнений
193
S3 = а [а (ft) (ft) + ft] [a (ft) (ft) + ft] + Ъ =
= а [а (ft) (ft)] [а (Ь) (ft)] + а [ft] [а (&) (ft)] + а [а (ft) (ft)] [ft] + а [ft][ft] + ft; теперь опустим скобки:
L2 = ab2 + ft;
L3 = a2b2ab2 + abab2 + a2ft3 + aft2 + ft.
Мы видим, что ряд действительно является характеристическим.
Заключение. КС-грамматикам могут быть сопоставлены системы уравнений, вторые члены которых суть многочлены с коэффициентами, равными 1 '). КС-языки являются опорными множествами положительных рядов, полученных в результате решения подобных систем; коэффициенты этих рядов показывают степень неоднозначности цепочек (т. е. число сопоставляемых им структур).
Остается выяснить, можно ли дать разумную лингвистическую интерпретацию рядам с коэффициентами любого знака и системам уравнений с не обязательно положительными коэффициентами. Мы рассмотрим этот вопрос в гл. XVI, посвященной алгебраическим языкам.
11.2.6. Упражнения
1. Пусть имеется язык Lm, порождаемый следующей нормальной грамматикой:
= А, В}; Vt = {a, ft, с}; аксиома — S; S-vaA S-vft? S-VC .
A -V Sa В -V Sft
Построить соответствующую этой грамматике систему уравнений и решить ее с помощью формальных рядов. Исследовать индуцированную структуру цепочек, сравнив ее со структурой, которую дает грамматика, рассмотренная в п. 11.1.5.
2. Пусть имеется грамматика
S-V SS S-V a S-vft
с аксиомой S и терминальным алфавитом {a, ft}.
Решить уравнение, соответствующее этой грамматике. Исследовать индуцированную структуру и неоднозначность цепочек. Обнаружить закон, по которому определяется степень неоднозначности,
') Это следует просто из того, что в грамматике нет двух одинаковых правил. — Прим. ред. Глава XII
ГРАММАТИКИ НЕПОСРЕДСТВЕННО СОСТАВЛЯЮЩИХ. АВТОМАТЫ С ЛИНЕЙНО ОГРАНИЧЕННОЙ ПАМЯТЬЮ
§ 12.1. ГРАММАТИКИ НЕПОСРЕДСТВЕННО СОСТАВЛЯЮЩИХ (НС-ГРАММАТИКИ) ')
12.1.1. Содержательное (лингвистическое) обоснование
Рассмотрим простую фразу, построенную по схеме Gni V Gn2 (группа подлежащего + сказуемое + группа дополнения: Мальчик ест яблоки, Мешок весит пуд, ...). Фиксируем семантический класс существительных, выступающих в функции вершин групп подлежащего и дополнения: названия одушевленных существ, названия абстрактных понятий и т. п.; тогда семантический класс глагола, который может быть сказуемым, зависит от этих семантических классов, т. е. класс допустимых V ограничен контекстом Gn1—Gn2.
Подобными ситуациями изобилуют и естественные, и искусственные языки; поэтому формализация указанного явления представляет очевидный интерес.
12.1.2. НС-грамматики
НС-грамматика — это совокупность следующих трех объектов: . конечный алфавит V= Va U Vt; Va (1 Vt = 0; .. аксиома SeVa, ... множество правил вида
ФИФ2->ФІШФ2,
где А є Va, фі, ф2 є V* и ш не пусто.
Подобные правила, интерпретируемые следующим образом: «В контексте ф1 (левый контекст) и контексте ф2 (правый контекст) нетерминальный символ А заменяется цепочкой ш», мы будем называть НС-правилами2).
Заметим, что КС-грамматики образуют подкласс НС-грамматик, соответствующий случаю, когда фі и ф2 пусты.
') В оригинале — grammaires a regies conlexluelles, т. е. «грамматики с кин-текстными правилами». Этот термин представляется нам неудачным, поскольку если мы примем его, то контекстно-свободные, или «бесконтекстные», грамматики окажутся частным случаем «контекстных». Принятый в русской литературе термин «грамматики непосредственно составляющих» (ср. англ phrase-structure grammars) объясняется тем, что грамматики этого класса сопоставляют порождаемым ими цепочкам системы (непосредственно) составляющих точно таким же образом, как являющиеся их частным случаем КС-грамматики. — Прим. ред.
г) В оригинале — английский термин context-sensitive, т. е. «контекстно-чувствительные»; ср. предыдущее примечание.—Прим. ред. Гл. XII. Грамматики непосредственно составляющих 195
