Введение в формальный анализ естественных языков - Ляпунова А.А.
Скачать (прямая ссылка):
S-Xi1; S-* а„. (6)
В этом тривиальном случае грамматика есть не что иное, как словарь предложений. Рассмотрим более интересный случай грамматики, состоящей из двух правил;
S -» aS; S-* а. (7)
Эти два правила могут породить любое из предложений а, аа, ааа, аааа, ...1) (очевидно, эти предложения могут быть поставлены во взаимнооднозначное соответствие с числами натурального ряда, так что язык будет счетным). Порождение предложения, например ааа, происходит следующим образом;
S (данный, начальный символ), aS (получается применением первого правила подстановки),
aaS (получается повторным применением первого пра- (8) вила подстановки), ааа (получается применением второго правила подстановки) .
1J Более точно следовало бы сказать, что мы рассматриваем грамматики с правилами вида ці,фі(і2-> ЦіфгЦг, где (it и — переменные, областью значений которых являются произвольные, быть может, пустые цепочки, а ф| и фг — постоянные. Ясно, что если ограничиться только правилами этого вида, то при формулировке правил переменные могут быть опущены*.
246
И. Хомский, Дж. Миллер
В дальнейшем мы будем изучать системы правил такого, а также более сложного видов.
Повторим еще раз, что грамматикой языка называется ко* печное множестио правил, задающие этот я;шк (что определение будет ую'шено и следующих разделах). Допустимой ни-ляется та грамматика, которая задает список (в общем случае бесконечный) предложений данного языка (т. е. список цепочек символов, которые являются предложениями). Грамматика должна быть, по определению, конечной. Если допустить грамматики с неопределенным множеством правил, то сама проблема построения грамматик снимается: можно просто принять в качестве грамматики бесконечное число предложений, что будет, конечно, бессмысленно-. Ясно, что грамматика должна играть роль теории повторяющихся закономерностей построения предложения, которые мы называем синтаксической структурой языка, В той мере, в какой грамматика формализована, она является математической теорией синтаксической структуры языка.
Очевидно, однако, что задачи грамматики не могут быть сведены к простому перечислению предложений язы'<а (хотя практически даже эта цель никогда еще не была достигнута). Мы потребуем, чтобы грамматика приписывала каждому порождаемому предложению его структурное описание, которое определяло бы, из каких элементов построено предложение, каков их порядок, расположение, и т. д., — в общем задавало бы всю грамматическую информацию, необходимую для того, чтобы определить, как это предложение используется и понимается. Теория грамматики должна, таким образом, включать некоторое устройство, позволяющее для любой заданной грамматики G и предложения s, порождаемого грамматикой G, определять, какое структурное описание приписывает грамматика G предложению s. Если рассматривать грамматику как конечно характеризуемую функцию, которая перечисляет язык как свою область значений, то можно считать, что лингвистическая теория должна определить функционал, который сопоставляет каждой паре (G, s), где G —- грамматика, a s—предложение, структурное оґіисание і по отношению к О; при этом одна из первоочередных задач лингвистической теории состоит, конечно, в том, чтобы дать ясное определение понятия «структурное описание».
Описанное понимание грамматики возникло недавно и может показаться непривычным. Несколько приводимых ниже примеров могут разъяснить, что здесь имеется в виду. Рассмотрим три искусственных языка, описанных Хомским (Chomsky, 1956).
Формальный анализ естественных языков
24 T
Язык L{. В Li входят предложения ab, aabb, aaabbb и т. д.; иначе говоря, в L1 входят все предложения, содержащие п вхождений буквы а, за которыми следует п вхождений буквы 6, и не мходит никаких других предложений.
Язык L1. В L2 входят предложения аа, bb, abba, baab, aabbaa и т. д.; иначе говоря, в Li входят все предложения с зеркальным отображением (т. е. предложения, содержащие данную цепочку, за которой следует та же цепочка с обратным порядком символов) и не входит никаких других предложений.
Язык Li. В L3 входят предложения аа, bb, abab, baba, aabaab и т. д.; иначе говоря, в L3 входят все предложения, в ко» торых за данной цепочкой следует та же цепочка, записанная еще раз, и не входит никаких других предложений.
Грамматика G1 языка Li может иметь следующий вид:
Дано: S,
FI : S-*ab,
F2:S-+aSb, (9)
где 5 играет роль аксиомы, a /rI и F2— это правила образования, с помощью которых из аксиомы могут быть выведены допустимые цепочки символов. Вывод происходит так, как описано в примере (8). Вывод заканчивается, если в грамматике нет правил, позволяющих произвести замену какого-либо символа в порожденной цепочке.
Аналогичным образом грамматика Gi языка Li может иметь следующий вид:
Дано: 5,
FI : S-*aa,
F2-.S-*bb,
F3 S-> aSa, (10)
FA '.S ^bSb.
Интересным и важным свойством языков L1 и L2 является то, что новые конструкции могут вставляться внутрь старых. Поэтому, например, в предложении aabbaa языка L2 имеется отношение зависимости между первым и шестым элементами; внутрь вставлено отношение зависимости между вторым и пятым элементами; и, наконец, в самой глубине расположена зависимость между третьим и четвертым элементами. В соответствии с определением грамматик Gі и G2 никаких ограничений на число таких вставленных друг в друга зависимостей в порождаемых цепочках не наложено.
