Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
І76
Н. Хомсшй
рамму вывода х в G, сверху вниз и слева направо. Для иллюстрации рассмотрим грамматику G с правилами
S-+СВ, С-+AS, A ^ а, В-+Ь, S-* с, (20)
порождающую язык
ancbn (21)
при помощи таких примерно выводов, как тот, который показан на рис. 9 для цепочки аасЬЬ. Соответствующее устройство
PDS M будет иметь команды (22), соответствующие виду (18),
и команды (23), соответствующие виду (19):
(a, A1, е)-ЧЛ,, е),
(Ъ, B1, е) (В,, е), (22)
S" е)’
А В
/ \ I (е, S1, е) + (С„ S),
1 / \ * (е, Cn е) (B1, е),
°/\\ (е> вп5H (s,. °). ;23)
Ij (е> С[, е) -> (Ai, С),
(е, Ar, е) (S1, е),
Рис. 9. Типичный вывод
предложения в языке (21). (е, Sr, С)~*(СГ, а).
При допущении цепочки аасЬЬ с выводом, показанным на рис. 9, M будет последовательно совершать следующие шаги, где первая колонка представляет входную ленту с рассматриваемым символом, выделенным жирным шрифтом, вторая указывает состояние блока управления, а третья представляет содержимое ленты памяти.
Вход Блок управления Память (PDS)
I. aacbb ? »
2. aacbb
Формальные свойства грамматик
177
3. aacbb C1 oS
4. aacbb A1 aSC
5. aacbb А aSC
6. aacbb S1 oSC
7. aacbb C1 aSCS
8. aacbb ¦ A1 aSCSC
9. aacbb Ar aSCSC
10. aacbb S1 aSCSC
11. aacbb Sr aSCSC
12. aacbb Cr a SCS
13. aacbb B1 oSCS
14. aacbb Br oS С S
15. aacbb Sr oSC
16. aacbb С, OS
17. aacbb B1 OS
18. aacbb# Br OS
19. aacbb# Sr O
20. aacbb# Z е
Очевидно, что устройство допускает все (и только) цепочки, порождаемые 0, используя свою ленту памяти для запоминания той части вывода порождаемой цепочки х, которая понадобится на следующем шаге работы, в то время как оно последовательно воспринимает цепочку х на свогй входной ленте. Кроме того, ясно, что эта конструкция является совершенно общей и может быть использована для любой нормальной грамматики. Отметим также, что автомат PDS, определяемый этой конструкцией в терминах разд. 1.4, является устройством PDS с ограниченным контролем. Отсюда мы заключаем следующее.
Теорема 17. Для любого заданного бесконтекстного языка L можно построить автомат PDS с ограниченным контролем, допускающий L.
Как показал Мэтьюз [41,421, этот результат частично распространяется на контекстные грамматики. Если задана контекстная
12 Заказ Ne 563
178
Н. Хомский
грамматика G, мы определяем прямой вывод (a left-to-right derivation) [соответственно обратный вывод (a right-to-left derivation)]Kaft вывод, удовлетворяющий следующему условию: если (®,ф)—последовательные строки этого вывода, то <?=хА<» и (соответственно
<р=шАх и ф—ч>%х). Таким образом, заменяется всегда самый левый (соответственно самый правый) нетерминальный символ. Мэтьюз показывает, что можно построить автомат PDS Ml-R, который будет допускать цепочку х тогда и только тогда, когда в G существует прямой вывод цепочки х, и aBTOMaTPDS M который будет допускать цепочку х тогда и только тогда, когда в G существует обратный вывод цепочки х. По теореме 6 разд. 1.6 отсюда следует, что языки, допускаемые устройствами Ml-R и являются бесконтекстными.
Следовательно, будет бесконтекстным и их объединение (теорема 20, разд. 4.3). Таким образом, если в контекстной грамматике G имеются только прямые и обратные выводы, эта грамматика будет порождать бесконтекстный язык1). Мы говорим, что контекстная грамматика строго контекстна, если порождаемый ею язык не является бесконтекстным. Тогда мы видим, что необходимое условие того, чтобы грамматика была строго контекстной, состоит в том, что некоторые терминальные цепочки этой грамматики не имеют ни прямых, ни обратных выводов.
Нетрудно показать, что эти соображения останутся в силе, если определить прямой вывод (обратный вывод), как такой, в котором заменяемый символ в каждой строке находится не далее чем на определенном фиксированном расстоянии от самого левого (соответственно самого правого) нетерминального символа этой строки (см. Мэтьюз, в печати). Таким образом, грамматика будет строго контекстной лишь в том случае, когда некоторые из ее терминальных цепочек имеют только такие выводы, которые ие являются ни прямыми, ни обратными в этом расширенном смысле.
Мы говорим, что D есть п-вставленный вывод, если п есть наибольшее число, такое, что D содержит две последовательные строчки хАуВфСу и xAtfwifBy, где из цепочек ?,'}* более короткая имеет длину п. Таким образом, в п-вставленном выводе имеется строка, в которой заменяемый символ стоит на расстоянии п символов либо от самого левого, либо от самого правого нетерминального символа этой строки. Отсюда можно заключить, что для того, чтобы грамматика была строго контекстной, необходимо, чтобы для любого п она могла бы порождать некоторое предложение только при помощи m-вставленных выводов, где m>n. Заметим, в частности, что в вы-
1) Предложенное Мэтьюзом [41 ] построение эквивалентного автомата PDS не приводит к цели; однако утверждение, сформулированное в этом предложении, верно, как показал А. В. Гладкий (см. его реферат иа эту работу в РЖ Математика, 1965, 4В427),— Прим, перее.
