Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Свойства конструкции W можно объяснить на примере. Рассмотрим грамматику (61), которая удовлетворяет условиям конструкции Sr н теоремы 34:
S-+AB, А -* SC, В -* DB,
(61)
A-+a, B^b, С-+с, D-+d.
Эта грамматика порождает язык, состоящий из всех цепочек a(dLbc)> dkb, и ставит им в соответствие структурное описание такого вида, как показано на рис. 10 (для случая і=/ — 1, 2). Заме-
*) Лаигендоеи, в действительности, строит процедуру Ф, которая работает в реальном масштабе времени; т. е. скобочная структура цепочки х, порождаемой грамматикой G, выводится процедурой Ф из выхода преобразователя T, сопоставленного с О, во время работы T иад х.
208
Н. Хомский
g тим, что G содержит как лево-
/ N. рекурсивные, так и право-реку-
/ \ рсивные элементы, хотя она не
А & содержит самовставляемых эле-
/ \ \ ментов, и что в данном случае
/ Y У V лево-рекурсивный элемент А до-
Il /\ минирует над право-реку рсив-I ::ёШ/ \ . иым элементом S. .Этот аример 'в с а о в иллюстрирует положение,{часто I / \ I I опускаемое или недопонимае-
J / \ Il мое), что, хотя конечный преоб-
:Р f f а *¦ разователь Т, который интер-
;| претирует предложения так же,
* * как грамматика G, конечно, чи-
тает эти предложения слева на-_ право при одном прохождении,
Рис. 10, Структурное описание JLirala rnpnvpT „тп лплжня
предложения, порождаемого грамма- отсюда не следует, что должна
тикой (61). быть какая-либо лево-правая
асимметрия в структурном описании этих предложений.
Класс К последовательностей, построенных из грамматики G (61), содержит последовательности (S), (S, A), IS, В), (SM1C) н (S, В, D).
Конструкция 1F производит следующие правила:
[ [Sl1 _ [SA I
j [SAj2 [SBl11 (шагом 2 конструкции (59))
I [SB J2 [S]2 J
[Szll1 -+ а [SAj2 (шагом 1 конструкции (59))
[SJ2 -*¦ [SACl1 [SACI2-* [SAJ2 [SBi1^HSBJ2 (шагом 1 конструкции (59))
[SBJ1-+[SBDl1) , „ .....
1 J (шагом 3 конструкции (59))
[SBDJ2 [SBJ1J
[SACJ1 с [SACJ2 1 /шагом j конструкции (59))
[SBDJ1 d [SBDJ2 Г
Эти- правила образуют грамматику G*, определяемую при помощи W. В соответствии с рис. 10 имеем вывод
(шагом 4 конструкции (59)) (62)
Формальные свойства грамматик
209
[Sb adbc [Si4]2
ISilli adbc [SBJ1
a [S^h adbc[SBDJ1
a lSB]t adbcd lSBD]t
a [SEDJ1 adbcdlSB]^
ad [SBDl2 adbcd [SBjDI1
ad [SBj1 . adbcdd [SSD],
adb [SB]2, adbcdd [SBJ1
adb [S]2 adbcddb [SBJ2
adb [S^lCJ1 adbcddb [Sj2
adbc [SyiCI2
Ясно, что последовательность нетерминальных символов, полученных в этом выводе, позволяет нам однозначно восстановить структурное описание, показанное на рис. 10. Действительно, автомат с правилами из примера (62) порождает предложение adbcddb, систематически обходя размеченное дерево рис. 10. Этот пример типичен; он показывает, каким образом устройство с конечной памятью может со поставлять с каждой цепочкой х, порождаемой нормальной грамматикой без самовставления G, структурное описание, которое грамматика G ставит в соответствие х, причем это структурное описание может иметь произвольную сложность.
Предположим теперь, что нам нужно применить эту конструкцию к нормальной грамматике G с самовставлением. Будем говорить, что преобразователь T порождает (х, у) подобно грамматике G, если T порождает (х, у) в том смысле, как это было определено выше (т.е. преобразует х в у, допуская х как конечный автомат), причем Ф~10/) есть структурное описание, которое грамматика G ставит в соответствие х. Тогда преобразователь 1F(G), построенный, согласно конструкциям (59) и (60), будет, действительно, порождать (х, у) подобно грамматике G для каждой пары (х, у), такой, что у есть структурное описание, которое грамматика G ставит в соответствие х, и такой, что у не включает никакого самовставления. Кроме того, увеличивая память преобразователя T (по-видимому, самый простой способ здесь состоит в присоединении ограничен-
14 Заказ № 563
210
Н. Хомский
ного устройства PDS), мы позволим ему переименовать самовстав-ляемые символы вплоть до получения любой ограниченной степени самовставляемости и далее работать, как прежде. В этом случае T может порождать (х, у) подобно G для всех таких пар (х, у), что у есть структурное описание, которое грамматика G ставит в соответствие х и которое может содержать только ограниченные степени самовставления. Как мы знаем из теоремы S3, это самое большее, чего мы можем достичь при помощи конечного устройства. Из результатов разд. 1.6 и 4.2 следует, что если мы разрешим преобразователю использовать неограниченную память PDS, то он может быть сделан строго эквивалентным любой нормальной грамматике G; заметим, в частности, что конструкции (18) и (19) из разд. 4.2 на самом деле являются лишь: тривиальными частными случаями конструкции (59), содержащими только разделы (1) и (2).
Приведенные рассмотрения четко ограничивают объем, в котором предложения, порождаемые бесконтекстной грамматикой, могут обрабатываться (т.е. допускаться или интерпретироваться) устройством с конечной памятью или человеком, не имеющим (или имеющим весьма ограниченные) вспомогательных средств для работы. Мы снова вернемся к этим вопросам в следующей главе.
