Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Введение понятия последовательной грамматики мотивировано той легкостью, с которой порождение в этой грамматике может быть осуществлено при помощи технического устройства. После того как правила разложения некоторого нетерминального символа А были применены и таким образом уничтожены все вхождения А в последнюю строку строящегося вывода, можно быть уверенным, что А не встретится ни в какой дальнейшей строке вывода. Ограничения этого рода (хотя для более общего случая, включающего трансформационные правила) были предложены и изучены в приложении к лингвистическому материалу в работе [40].
Определение 7. Введем обозначения:
)-=(L I L порождается линейной грамматикой|,
)-i=jL j L порождается односторонней линейной грамматикой], )-м—(L ] L порождается мета-линейной грамматикой],
4 — [L I L порождается нормальной грамматикой), a — (I I L порождается последовательной грамматикой),
7 = (L j L порождается бесконтекстной грамматикой].
Таким образом, например, является множеством регулярных языков, как мы только что видели. С точки зрения порождающей
174
И. Хомский
способности эти системы соотносятся друг с другом следующим образом1) .
Теорема 16. а) Це тс.у [7, 69);
Ч + ф
б) ч = і [8]; в) X1Cazif [20].
Языки L1 и L2 порождаются линейными грамматиками, но, как мы уже видели в разд. 1.1, не порождаются конечными автоматами (односторонними линейными грамматиками). Произведение языков L1 и L2 из I принадлежит Xm , но в общем случае не принадлежит X. Множество правильно построенных формул исчисления высказываний в бесскобочной записи является примером языка, который не имеет мета-линейной грамматики, но порождается бесконтекстной грамматикой
S -s. CSS, S -> NS, S -s. V, V -> V', V -> р, (15)
где р, р',р",...— пропозициональные переменные, С — знак импликации, N — зиак отрицания.
Языки Ll(— \апЬп)) и L2( = \хх*)х есть цепочка в алфавите
I а, Ь\ и х*— зеркальное отражение х}) принадлежат о, но не принадлежат X1. Примером языка из f, не принадлежащего о, является язык со словарем \а, Ь, с, dj, содержащий предложение
a"2*-1 d ... dbn‘‘da"1 са"1 dbn* d... (16)
(симметричное относительно с) для каждой последовательности (k, H1,.целых положительных чисел. Этот язык порождается грамматикой с правилами
S -> adAda, S aSa, S аса,
A^bAb, A -*¦ bdSdb (17)
(которые, впрочем, линейны), но не порождается последовательной грамматикой.
Так как нормальные грамматики могут порождать любой бесконтекстный язык, общее условие, сводящее грамматику к разложению на бинарныесоставляющие и, отдельно, к лексикону, не ограничивает порождающей способности более, чем ее ограничивает общий класс бесконтекстных грамматик (хотя, конечно, это условие весьма ограничивает системы порождаемых структурных описаний, т. е. ограничивает сильную порождающую способность).
1) Знак с. понимается здесь как строгое включение, исключающее слу-чай равенства,— Прим. перев.
Формальные свойства грамматик
175
4.2. Бесконтекстные грамматики и ограниченно-бесконечные автоматы
Мы видели, что бесконтекстные и контекстные грамматики различного вида, рассматривавшиеся нами, по своей порождающей способности превосходят конечные автоматы, но не достигают возможностей общих систем подстановок (машии Тьюринга). В частности, мы иашли языки, которые не регулярны, но порождаются линейными бесконтекстными грамматиками (даже с одним нетерминальным символом). С другой стороны, мы заметили, что даже контекстные грамматики могут порождать лишь рекурсивные множества и то не все. Грамматики того вида, который мы сейчас рассматриваем, принадлежат к категории ограниченно-бесконечных автоматов (разд. 1.3 — 1.7). В случае бесконтекстных языков мы видим, что каждый из них допускается линейно-ограниченным автоматом специального вида, использующим магазинную память (PDS) (ср. с разд. 1.4—1.6), и что такими устройствами могут допускаться только бесконтекстные языки.
Чтобы показать это, ограничимся рассмотрением нормальных грамматик, это не приведет к ,потере общности [ср. теорема 16 (б) I. Можно также без потери общности допустить, что если A-^-BC есть правило грамматики, то ВфС. Если задана такая нормальная грамматика G1 мы можем построить автомат PDS AT, который будет допускать язык L(G)1 следующим образом. Для каждого нетерминального символа Л из G блок управления M будет иметь два состояния A1 и Л,. Для каждого правила A-^a из G автомат Al будет иметь команду
(a, A1, е) -* (Aj, е). (18)
Для каждого правила A -+ BC из G автомат M будет иметь команды:
(е, A1, е) -> (B1, А),
(е,Вге)^(С(,е), (19)
(е, Cr, A)-, (An а),
где е — единичный элемент. Следовательно, в общем случае Al будет «детерминированным автоматом PDS. Его начальное состояние мы обозначим символом E1 i.e встречающимся в G. Устройство имеет команды (е, Е, а) (S1, е) и (е, Sr, о) > (?, а), где S — начальный символ G, позволяющие ему переходить из ? в Sf и из Sr в Е, стирая о и закашивая работу.
Автомат M допускает цепочку х, порождаемую грамматикой G, систематически обходя кругом дерево, представляющее диаг-
