Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
б) Из определения L-регулярного укрупнения следует — так как взаимозамещаемость является конгруэнцией,— что если X, Уе (V/pi)* и r)i2(^) to
X ?Й' Y. Поэтому, если t]i2{X) = Ze02(i) и z — про-е, (D
извольная цепочка из L такая, что 02(z) =rii2(0i(гг)) = = Z, имеем X 0! (z), откуда X (= 0i(L).
e,(i.)
Теорема ПП.З. Если р2 — L-регулярное укрупнение Pi, то:
а) X =#> Y тогда и только тогда, когда т]12(Х) =#> t]i2(K);
в ,(?.) ег(?.)
б) X является конфигурацией ранга г языка 0! (L) с результирующим А тогда и только тогда, когда Л12 (^) является конфигурацией ранга г языка 02 (L) с результирующим г]12(Л).
326
ЗАМЕЩАЕМОСТЬ
[П. И
Доказательство, а) Пусть X Y, и пусть Z,,
е.а)
Z2 — произвольные цепочки из (V/p 2)* такие, что ZiT[\2 (X) Z2 е 02 (L). Если Ть Т2 — произвольные ^^-прообразы цепочек Z, и Z2 соответственно, то ti12(7’1.XT2) = = ZiX]i2(X) Z2, откуда по лемме ПП.З TiXT2 е 0i(L); отсюда следует TiYT2^Qi(L) и—снова по лемме ПН.З— y\\i(TiYT2) = Zir\i2{Y)Z2 е 02(?). Аналогично доказывается, что rii2(^)=^> г)12 (У) влечет X =ф> У.
е2ц.) e,(i.)
б) При г = 1 утверждение справедливо в силу а). Пусть оно доказано для всех i < г, и пусть X — конфигурация ранга г языка 0j(L) с результирующим А. Пусть Z1; Z2 — цепочки из (У/р2)\ Г1; Г2 — произвольные их т]12-прообразы, и пусть при этом цепочка Zxr\\2(X)Z2 принадлежит 02(L) и не содержит вхождений конфигураций рангов, меньших г, языка 02(L), перекрывающихся с выделенным вхождением т]12(Х), но не содержащихся в нем целиком. Тогда в силу индуктивного предположения цепочка ТхХТ2 не будет содержать вхождений конфигураций рангов, меньших г, языка 0t(L), перекрывающихся с выделенным вхождением X, но не содержащихся в нем целиком; следовательно, поскольку ТхХТ2 е 0! (L), имеем ТХАТ2 е 0, (L), откуда Z,t]]2(A)Z2 е <= 02 (L). Кроме того, в силу а) будет г\12 (Л) =# т]12 (X). Итак,
Ш)
ri12(X) есть конфигурация ранга г языка 92(L) с результирующим Т112(Л). Обратное доказывается аналогично.
Лемма ПП.4. Если р2 — L-регулярнсе укрупнение р{ и р3 — L-регулярное укрупнение р2, то р3 есть L-регуляр-ное укрупнение
Доказательство. Пусть Л, Л'еУ/рь СеУ/ р3) Л, Л'?С. Положим Г112(Л) = Й, т]12 (Л') = .6'. Поскольку ЛеВ и Л' Е В', пересечения В П С и В' f| С не пусты и, следовательно, Б = С, В' ЕС; поэтому Б О Д', от-
e2(i.)
куда по теореме ПП.З Л Л'.
еди
Из леммы ПП. 4 немедленно вытекает Теорема ПП. 4. .Если р' — L-производная эквивалентность для р и р" — L-производная эквивалентность для р', то р" совпадает с р'.
Рассмотрим теперь эквивалентность, L-производную для равенства. Эта эквивалентность есть, очевидно, не
§ ПИ.3]
ОКРЕСТНОСТИ, КЛАССЫ И ТИПЫ
327
что иное, как взаимозамещаемость относительно L, ограниченная цепочками длины 1. Для этой эквивалентности мы будем, наряду с записью ФФ, пользоваться
V.L
также обозначением SL; соответствующие классы эквивалентности будем называть семействами. Разбиение на семейства, т. е. на классы «синтаксически эквивалентных» ЛЗ-сегментов, представляет собой, видимо, единственную содержательно интересную классификацию слов, точнее, ЛЗ-сегментов, которую можно получить, исходя лишь из языка L, т. е. пользуясь только понятием грамматической правильности и не принимая во внимание лексических значений, как мы до сих пор фактически поступали*). Чтобы получить другие классификации, в частности такие, которые могли бы служить в какой-то степени моделями понятий части речи, грамматического рода и т. п., нужно учитывать и лексические значения. А поскольку элементарный символ, т. е. ЛЗ-сегмент, является для нас неразложимой единицей, лексические значения тем более неразложимы, и поэтому их учет не может означать ничего другого, кроме включения в число исходных данных сведений о том, какие ЛЗ-сегменты отвечают одинаковым лексическим значениям и какие — разным. Иначе говоря, мы должны считать заданными множества ЛЗ-сегментов, имеющих одинаковые лексические значения, т. е. являющихся «формами одного слова». Эти множества мы назовем окрестностями. Примеры окрестностей для русского языка: {физик, физика, физику, физиком, физике, физики, физиков, физикам, физиками, физиках}, {пальто}, {над}**).
*) Это означает, что элементарные символы во всех предыдущих рассмотрениях можно было бы интерпретировать и как сегменты (ср. стр. 315). Конкретные результаты зависят, разумеется, от выбора интерпретации. Например, сегменту физику отвечают два ЛЗ-сег-мента, скажем а\ — с лексическим значением, включающим компонент «наука», — и а2 — с лексическим значением, включающим компонент «специалист»; в то же время для сегментов химию и химику имеется по одному ЛЗ-сегменту — пусть это будут бис. Трактуя предложения как цепочки ЛЗ-сегментов, получим а\ Ь, а2 с, а при отказе от учета дексических значений сегменты физику, химию и химику распределятся по трем разным семействам.
**) Здесь для простоты вместо ЛЗ-сегментов выписаны сегменты; необходимое уточнение очевидно — например, вместо сегмента физику следовало бы взять ЛЗ-сегмент а2 из предыдущей сноски.
328
ЗАМЕЩАЕМОСТЬ
