Введение в формальный анализ естественных языков - Ляпунова А.А.
Скачать (прямая ссылка):
Формальный анализ естественных языков
255
используемые в этой и двух следующих главах. В этом разделе мы рассмотрим грамматику G:
G = IV,-, Vr, 5, й],
которая представляет собой систему е операцией соединения, удовлетворяющую следующим условиям.
1. V есть конечный набор символов, называемый словарем.
Цепочки символов этого словаря получаются с помощью операции соединения это ассоциативная и некоммутативная
бинарная операция над цепочками в словаре V. Если не возникает неоднозначности, символ ~ может опускаться.
2. Vr с: V. Мы называем Vt терминальным, словарем. Дополнение к Vt относительно V называется нетерминальным, или вспомогательным., словарем и обозначается Vw.
3. Отношение —* есть конечное, двуместное, иррефлексивное и асимметричное отношение, имеющее место для конечного числа пар цепочек в алфавите V и интерпретируемое как «подставляется вместо». Пары < ф, >, такие, что <р —* \|), называются (грамматическими) правилами грамматики G.
4. Если A ? V, то А ? Vjv тогда и только тогда, когда существуют цепочки такие, что фА\|) —> фю\|>. При этом
tt t VT; S 6 Vn; е? Vt, где it есть граничный символ; 5 — начальный символ, который можно читать как «предложение»; е есть единичный символ, обладающий тем свойством, что для ВСЯКОЙ цепочки ф, еф = ф = фе.
Введем еще следующие дополнительные обозначения.
5. Последовательность цепочек D—(фЬ ..., ф„) («>• 1)
есть ф-вывод цепочки ?, тогда и только тогда, когда выполняются следующие условия:
а) ф = фь ф = фп;
б) ДЛЯ ВСЯКОГО І < П существуют цепочки фі, ф2, X, м, такие, ЧТО X -КВ, ф,= Ч>1ХЧ>2 И фі+1 = Фі®Ч>2.
Очевидно, множество выводов полностью определяется заданием отношения —>, т. е. конечным множеством грамматических правил. Если существует ф-вывод цепочки ?, мы говорим, ЧТО ф подчиняет Ij), и пишем ф=ф»1?; отношение является, таким образом, рефлексивным и транзитивным.
6. ф-вывод D цепочки \|> называется терминальным, если ijj есть цепочка в Vt h D не является собственным началом некоторого другого выаода (заметим, что эти условия !независимы).
7. i|) есть терминальная цепочка грамматики G, если для цепочки ft S tt имеется терминальный tt Sfl:-вывод; иначе говоря, терминальная цепочка — это (с точностью до граничного
256
И. Хомский, Дж. Миллер
символа) последняя строка терминального вывода, начинающегося с цепочки tt Sft .
8. Терминальным языком, порождаемым грамматикой G, называется множество терминальных цепочек грамматики G.
9. Дне грамматики Cj и G* (слабо) эквивалентны, если они порождают один и тот же терминальный язык. Понятие сильной эдиипаленлшети рассматривается ниже.
Естественно, чтобы граничный символ Д удовлетворял тому условию, ЧТО если ( Фі, ..., ф„) ЄСТЬ Д S Д- ВЫВОД, то для всякого І, такого, что ф[ = Д tt> 1I3; не содержит Д. Чтобы обеспечить выполнение этого условия, мы наложим на правила грамматики (т. е. на отношение —») следующее дополнительное условие.
10. Если од ... CCm-* Pt ••• Pn есть правило грамматики (где at, ..., am, Pb ,.., pn 6 Vr— {е}), то
а) Д для I <i <п\
б) Pi= Д, тогда только тогда, когда ai= Д ;
в) р„ = Д, тогда и только тогда, когда ат=Д,
Все эти условия пока еще ничего не говорят о том, как может грамматика обеспечить С-маркер для каждой цепочки. Это требование мы будем иметь в виду при рассмотрении добавочных ограничений на грамматику.
Cm. работу Чулика (Culik, 1962), где содержится критика более раиних определений грамматики, изложенных в работе Хомского (Chomsky, 1959).
Возвращаясь теперь к понятию рекурсивного элемента из разд. 3, мы можем заметить, что для всякого A g Vn имеют место следующие утверждения.
1. Если имеются непустые цепочки ф, 1|з, такие, что
Л=ф фАф, то А есть самовставленный элемент.
2. Если имеется непустой элемент ф, такой, что АгфЛф,
то А есть леворекурсивный элемент. .. ..
3. Если имеется непустой элемент ф, такой, что А=}(рА,
то А есть праворекурсивный элемент.
4. Если А есть нерекурсивный элемент, то не существует
таких цепочек ф, что .А=фф.АЧ>.
Обратные утверждения ие обязательно верны для всех грамматик, которые мы рассматривали до енх пор, однако онн будут верны для того случая, который мы будем рассматривать ниже. Предположим, что грамматика G содержит правила S-*ВАС, BA—^BBAC1 но не содержит правила А—*% ни Лля какого х- Тогда не существует цепочек ф, ijj, таких, что
Формальный анализ естественных языков
257
.Д=фф.А»|), хотя А является рекурсивным (а именно самовста-вленным).
При рассмотрении систем такого рода «еобходимо отличать терминальные цепочки от нетерминальных, а также отдельные (атомарные) элементы от цепочек, образованных их соединением. Чтобы последовательно соблюдать это различие, удобно придерживаться следующих обозначений:
Тип (элемента или цепочки) Элементы Цепочки
Нетерминальные A, Bt С, . , X, У, Z1 . . .
Терминальные а, Ь, с, . . . х, у, г, . . .
Произвольные а р, V. • • • ф' ъ ?, • • •
В предыдущем изложении мы уже фактически придерживались этого соглашения; оно будет использоваться далее до конца работы без дополнительных комментариев.
