Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
цепочку р!...рь где р,.........pft<=F/p2, такую, что
otjsPj, a*spfe. Ясно также, что 01,п12 = 02. Отображение т)12 мы также будем называть алфавитным гомоморфизмом. (Понятие, рассматривавшееся до сих пор под этим названием, становится частным случаем только что введенного, если заменить V на F/=, где =« — отношение тождества.)
318
ЗАМЕЩАЕМОСТЬ
[П. I
§ ПН. 2. Замещаемость и взаимозамещаемость. Конфигурации
Пусть V — произвольный словарь, L — язык в ело; варе V и х, у ^V*. Будем говорить, что цепочка замещаема на цепочку у относительно сл варяКиязыкаЬ, и писать х =# у, если Va, oeF* [uxv -
V, L
sLd uyv e L] *). Если каждая из цепочек х, у замеща ма на другую относительно V и L, говорим, что х и взаимозамещаемы относительно V и L, пишем х^у. (Буквы V и L будут опускаться, если нед
V, L
разумение невозможно.) Запись ФX{V, L) будет означа {у\х^у}, запись Ф(К, L) будет означать {(х, у)\х=^у v, l v, l /
аналогично, с заменой =Ф на О, определим ^(К, Ь и 'Р (V, L). При невозможности недоразумения буква в этих обозначениях будет опускаться.
Легко убедиться, что для произвольного языка в произвольном слова ре V отношение О является ко
V.L
груэнцией на свободной полугруппе V*. д
Будем говорить, что отношение эквивалентности на свободной полугруппе V* согласовано с языко L Е V*, если для любых двух цепочек х, г/ е F* изхе и x@ty следует y^L.
Лемма ПП. 1. Отношение ФФ согласовано с яз
V, L
ком L и является укрупнением любой конгруэнции на V согласованной с L.
Доказательство. Согласованность ФФ с L н :
V.L
посредственно вытекает из определений. Пусть Ш. — ко груэнция на V*, согласованная с L, х, и х$,у
Тогда для любых г, иеУ* будет zxu&zyu, и поэтом zxueL влечет zyu&L; таким образом, х=Фг/. Анало
*) Ясно, что если L^V\, LsVj, х, y^V\, х, у&У*2, т
х=фу равносильно х=^у. Однако обозначение =ф удобно в слу V,, L V„ L V, L
чаях, когда отношение рассматривается «в целом», как множ ство пар. ^
§ mi.2)
замеЩаемость и ВЗАИМОЗАМЕЩАЕМОСТЬ
319
гично имеем у=^х. Итак, всякий ^-класс содержится v, L
в некотором -классе.
V, L
Лемма ПП. 1 позволяет утверждать, что среди всех конгруэнций на V*, согласованных с L, отношение имеет наименьший индекс.
V, L
Лингвистический смысл понятия взаимозамещае-мости состоит приблизительно в следующем. Если интерпретировать V как множество ЛЗ-сегментов *) некоторого естественного языка и L — как множество грамматически правильных фраз этого языка, то взаимо-замещаемые цепочки будут представлять собой «синтаксически эквивалентные», т. е. выполняющие одни и те же синтаксические функции, словосочетания. Так, в русском языке цепочку высокому дому можно, видимо, считать взаимозамещаемой с цепочкой умному совету, стене — с доске, исключительно важными — с важными.
Пусть теперь а <= V, VV+ (так что \х\ > 1) и а^х. Мы будем говорить в этом случае, что х есть
L
конфигурация 1-го ранга языка L с результирующим а.
При указанной выше лингвистической интерпретации словаря V и языка L конфигурации 1-го ранга будут «потенциальными составляющими», т. е. цепочками, которые могут входить в лингвистически естественные системы составляющих грамматически правильных предложений данного языка. Так, в русском языке цепочка исключительно важными является, видимо, конфигурацией 1-го ранга с результирующим важными (а также с любым из результирующих ценными, вредными, скверными, ...); существуют, очевидно, правильные русские предложения, для которых эта цепочка входит в число «естественных» составляющих [например, (Эти работы) (являются (исключительно важными))].
Однако «потенциальные составляющие» заведомо не исчерпываются конфигурациями 1-го ранга. Например, словосочетание важными работами является «потенциальной составляющей» [ср. Я (((не был) знаком) ((с (важными работами)) Иванова ))]; в то же время
*) Ср., впрочем, сноску *) на стр. 327.
320
ЗАМЕЩАЕМОСТЬ
in. П
ясно, что на это словосочетание могут быть замещаемы только такие цепочки, как работами, лекциями, шапками, докладами, собаками, ушами *) и т. п., и поэтому, если бы цепочка важными работами была конфигурацией 1-го ранга, то только с такими результирующими. Но, например, в фразе Я не был знаком с исключительно важными работами Иванова нельзя без нарушения грамматической правильности заменить важными работами ни на работами, ни на лекциями, ни на собаками; ушами и т. п. Такая замена возможна лишь в тех контекстах, где нет словосочетаний вроде исключительно важными или невероятно важными, перекрывающихся с заменяемым вхождением словосочетания важными работами. Эти соображения приводят к следующему определению.
Пусть г > 1 — натуральное число, и для каждого t, 1 «g; I < г, определено понятие конфигурации ранга i языка L. Тогда цепочка х е VV+ называется конфигу-рацией ранга г языка L с результирующим а, где се F, если выполняются следующие два условия:
1) х; 2) если ZiXZ2^L и цепочка zixz2 не содержит вхождений конфигураций рангов, меньших г, перекрьь вающихся с выделенным вхождением х, но не содержащихся в нем целиком, то ziaz2 е L.
