Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
« ПП.З]
ОКРЕСТНОСТИ, КЛАССЫ И ТИПЫ
331
как легко убедиться, совпадают с окрестностями. В частности, особый тип образуют все формы слова новый\ легко понять, что если бы мы добавили к V" еще какие-нибудь прилагательные, соответствующим образом расширив L" и доопределив Г", то все прилагательные составили бы один класс и один тип (а прочие классы и типы остались бы без изменения).
Таким образом, классы в (V", L", Г") попарно не пересекаются, так что отношение «принадлежать одному классу» есть эквивалентность на Vi". Сразу видно, что эта эквивалентность является //'-регулярным укрупнением Г" и ее ^'-производная эквивалентность совпадает с Ti”, г". Следующие рассмотрения показывают, что такая же ситуация имеет место для всякого однородного лексически размеченного языка.
Теорема ПП. 5. В однородном лексически размеченном ,языке всякий класс порождается любым семейством (любой окрестностью), пересекающимся (-ейся) с ним.
Доказательство ввиду замечания, сделанного после определения однородности, достаточно провести для случая класса, порожденного семейством.
Пусть (V, L, Г) —однородный лексически размеченный язык и х— класс, порожденный семейством а. Рассмотрим произвольное семейство а', пересекающееся с х, и порожденный им класс х'. Условие о' П х ф 0 означает, что о' пересекается с некоторой окрестностью, пересекающейся с о; поэтому, по вышеупомянутому замечанию, любая окрестность, пересекающаяся с а, пересекается и с о', и обратно, что дает х = х'.
Пусть теперь у — произвольная окрестность, пересекающаяся с х, и х"— порожденный ею класс. Окрестность у пересекается с некоторой окрестностью, пересекающейся с о, и, значит, совпадает с ней; таким образом, у П о ф 0. Если аех, то Г (а) пересекается с о и, стало быть (пр определению однородности), SL(a) пересекается с у, что означает SL(a) ^ х", так что аех". Следовательно, к?х". Если 6 6 х", то SL(b) пересекается с у; поэтому, по использовавшемуся выше замечанию, Г(Ь) пересекается с о, т. е. Г(6) 9х и бек; итак, х" ? х.
332
ЗАМЕЩАЕМОСТЬ
[П. II
Замечание. Обращение этой теоремы также справедливо, и притом в усиленной форме (см. упражнение ПП. 10).
Следствие. Если (V, L, Г) — однородный лексически размеченный язык, то любые два его класса либо совпадают, либо не пересекаются. Иначе говоря, существует эквивалентность Кь.т на V такая, что аКь.тЬ тогда и только тогда, когда а и b принадлежат одному классу.
Ясно, что Kl,f является укрупнением для SL и для Г, Но сверх того имеет место
Теорема ПП. 6. Если (V, L, Г) — однородный лексически размеченный язык, то Кь,т является L-регулярным укрупнением Г.
Доказательство. Нам нужно показать, что в условиях теоремы любые две окрестности, содержащиеся в одном классе, взаимозамещаемы относительно языка 0г (L), где 9г — алфавитный гомоморфизм V* на {V/T)*. Пусть х — класс, Yi и Y2 — окрестности, содержащиеся в х, и 1, 11 — цепочки окрестностей такие, что Iyi1! е 9г (L). Тогда найдутся такие цепочки х, уеУ* и такое ае^, что 0гМ = ?, 0г(г/) = 'П и хаг/eL. Ввиду однородности (V, L, Г) класс х порождается некоторым семейством, а отсюда по той же причине следует, что в у2 найдется элемент Ь, взаимозамещаемый с а, так что xby^L, и поэтому IY2T1е 9г (?)• Итак, Yi=^Y2; обратное доказывается так же.
Пусть теперь Kl.v — L-производная эквивалентность для /Cl, г- По теореме ПП.6 и лемме ПП.4 K'l.t есть L-регулярное укрупнение Г; поэтому TL% г является укрупнением KL, г- В то же время по теореме ПП.З из взаимозамещаемости двух окрестностей относительно 0r(L) следует взаимозамещаемость содержащих эти окрестности классов относительно 0^L_ г(L) (QKl г — алфавитный гомоморфизм V* на (У/Кь.гУ), а это означает, что KL г есть укрупнение TLt г- Итак, К1, г = Tl, г-
В русском языке однородность имеет место лишь для «малых» фрагментов, наподобие рассмотренного в примере 1; как мы сейчас увидим, при существенном расширении этого фрагмента однородность не сохраняется. Но для языков с более простой системой именного словоизменения (идеальный случай — эсперанто)
§ ПП.З]
ОКРЕСТНОСТИ. КЛАССЫ И. ТИПЫ
333
можно, видимо, обеспечить однородность и в довольно представительных моделях.
Понятие класса может, впрочем, служить основой содержательно интересных «категоризаций» и при отсутствии однородности; что же касается понятия типа, то на его лингвистическую интерпретацию условие однородности, видимо, существенным образом не влияет. Проиллюстрируем это на примере, которым мы и завершим настоящее приложение.
Пример 2. Расширим построенный в примере 1 лексически размеченный язык (V", L", Г"), добавляя к L" последовательно следующие предложения:
1) все предложения, получаемые из прежних заменой форм единственного числа существительных и прилагательных соответствующими формами множественного числа *) и одновременной заменой придаточного который (-ая, -ое) всем понравился (-ась, -ось) другим придаточным: один (одна, одно) из которых всем понравился (-ась, -ось), причем должна сохраняться грамматическая правильность **);
2) все предложения, получаемые из имеющихся после предыдущего шага заменой форм существительных и прилагательных формами любых других существительных, соответственно прилагательных, с сохранением грамматической правильности, а также выбрасыванием прилагательных ***);
