Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Гладкий А.В. -> "Формальные грамматики и языки" -> 116

Формальные грамматики и языки - Гладкий А.В.

Гладкий А.В. Формальные грамматики и языки — Москва, 1973. — 368 c.
Скачать (прямая ссылка): formalnieidialogi1973.djvu
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 136 >> Следующая

В русском языке словосочетание важными работами является, по-видимому, конфигурацией ранга 2 с результирующим работами, или шапками, или лекциями и т. п.
Замечания. 1) Из определения ясно, что всякая конфигурация ранга г является и конфигурацией любого большего ранга с тем же результирующим.
2) Понятие конфигурации зависит, вообще говоря, от словаря, в котором рассматривается язык: при добавлении к словарю новых символов, не входящих в цепочки языка, могут возникать новые конфигурации (см. упражнение ПП.З). В дальнейшем мы всегда, если не оговорено противное, будем считать, что язык рассматривается в своем «наименьшем» словаре, состоящем в точности из тех символов, которые встречаются в его цепочках. Если рассматривается одновременно несколь-
*) Впрочем, при достаточно широком охвате русских предложений последние три цепочки не будут замещаемы на важными работами (ср. ниже, § ПП. 3, пример 2).
§ ПП.2] ЗАМЕЩАЕМОСТЬ И ВЗАИМОЗАМЕЩАЕМОСТЬ 321
ко языков, то подразумевается словарь, являющийся объединением соответствующих «наименьших».
Будем называть цепочку, принадлежащую языку L, неприводимой, если она не содержит вхождений конфигураций этого языка. Множество неприводимых цепочек языка L будет обозначаться Б (L).
Конфигурацию ранга г языка L назовем простой, если она не содержит вхождений конфигураций ранга г (или, что то же самое, рангов, меньших или равных г) этого языка, отличных от нее самой.
Пусть Т — некоторое множество конфигураций языка L и Ti — множество всевозможных упорядоченных пар вида (х, а), где хеТ и а — результирующий конфигурации х. Если Т — множество всех конфигураций, соответственно всех простых конфигураций, языка L, то 7\ будет обозначаться K(L), соответственно П(Ь). Упорядоченную пару (B(L), K(L)), соответственно (B(L), Я(L)), мы будем называть полной, соответственно приведенной, конфигурационной характеристикой языка L.
Лемма ПП. 2. Пусть Li, L2sF*. Если Б (Li) s <=B(U) и n(Li) c=K(L2), to U <=L2.
Доказательство. Пусть x e Индукцией no |x| покажем, что x e L2. Если |x|= 1, то из x e L4 следует x e Б (Li) s Б (L2) s L2. Допустим, что для цепочек длины, меньшей «(«> 1), утверждение доказано и | х | — п. Если при этом х е Б (Li), то х е Б (L2) s L2. Если же x^E(Li) и г — наименьший ранг конфигураций языка Li, содержащихся в х, то х содержит и простую конфигурацию w ранга г языка L; для некоторых ги z2^V* и b^V имеем х = zywz2 и (w, b)<=n(Li). Поскольку х не содержит конфигураций языка L рангов, меньших г, получаем zibz2 е но \zxbz2\ < «, откуда по индуктивному предположению zibz2 е и, поскольку (да, b) (= ^(Lj) = K(L2), х = ZiWZ2 (= L2.
Из леммы ПП. 2 непосредственно вытекает
Теорема ПП. 1. Пусть L4, L2e V*. Если ?>(Lt) = — B(L2) и либо К (Li) = K(L2), либо n(Li) = П (L2), го Li = L2.
Иначе говоря, язык в заданном словаре вполне определяется своей полной или приведенной конфигурацион-ной характеристикой.
П А. В. Гладкий
322
ЗАМЕЩАЕМОСТЬ
[П. II
Для лингвистических приложений особо интересным представляется класс языков, у которых Б и П конечны. Такие языки мы будем называть конечно характеризуемыми. Кажется в высшей степени правдоподобным, что в естественных языках при всяком разумном уточнении понятия грамматической правильности все правильные предложения и все конфигурации будут содержать вхождения некоторых словосочетаний стандартного вида («прилагательное + наречие», «существительное + прилагательное» и т. п.), являющихся простыми конфигурациями, и поэтому естественные языки (точнее — множества правильных предложений естест- ^ венных языков) конечно характеризуемы. (В то же время множество всех конфигураций естественного языка, видимо, бесконечно. Так, в русском языке сочетание существительного с любым числом определяющих его прилагательных будет конфигурацией.)
Проиллюстрируем нахождение конфигурационных характеристик на примерах.
Пример 1. Пусть L= {ge, аае, abde, bdae, bdbdi cf, def, efe, fff}. Заметим прежде всего, что для произвольного языка и произвольного символа а из его «наименьшего» словаря множество Фа содержит только такие цепочки, которые входят в цепочки данного языка в качестве подцепочек. Поэтому для конечного языка все Фа конечны, и, следовательно, К и П (равно как и Б) тоже конечны и могут быть найдены перебором. Положим Ф«(L) = {х|л: <= Фа(Ь)&|х | > 1}. Из предшествующего замечания ясно, что если язык L конечен и символ а входит в какую-либо цепочку языка L, имеющую наибольшую возможную для цепочек из L длину, то Ф'а(Ц пусто. Поэтому в нашем случае Ф& = Ф^ = Фе=0. Множество Ф? также пусто, так как иначе язык L содержал бы цепочки вида dex, где |*|> 1. Непосредственно проверяется, что bd е Ф^; других цепочек Ф^ не содержит, иначе язык L содержал бы цепочки вида xbde, где \х\ >1 и xi=bd. Аналогичным образом легко убедиться, что Ф'с — {de, ff}, Фй = {аа, abd, bda, bdbd, ef}. Непосредственно ясно, что цепочки аа, abd, bda и bdbd замещаемы на g и bd — на а, а также, что de и ff не замещаемы на с и ef — Hag. Итак, L имеет пять конфигураций 1-го ранга: bd, аа, abd, bda, bdbd. Далее, de
Предыдущая << 1 .. 110 111 112 113 114 115 < 116 > 117 118 119 120 121 122 .. 136 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed