Гладкий - Формальные грамматики и языки - 1973 (947381), страница 63
Текст из файла (страница 63)
гому ЛЗ-сегменту. В дальнейшем мы будем понимать элементарные символы как ЛЗ-сегменты. Впрочем, до некоторого момента будет допустимо также и понимание их как сегментов; место, начиная с которого введение лексических значений существенно, будет явно ука. вано (стр. 327 — 328). 5 П111 Свободные полугруппы Этот параграф вспомогательный; в нем излагаются некоторые простые алгебраические понятия, которые по.
надобятся нам в дальнейшем. Множество с определенной на нем ассоциативной бинарной операцией называется пол у г р у п и ой. Для обозначения полугрупповой операции обычно используется мультипликативная запись: результат операции над элементами х и у (в этом порядке) обозначается ху. Элемент е полугруппы 5 называется ед и ни цей, если для любого хеи5 имеет место хе = ех =х.
Легко видеть, что если полугруппа содержит единицу (что не обязательно), то только одну. Пусть 5 — полугруппа и М ~ 5; если 5 обладает единицей е, обозначим через 5 множество 3 — (е); в противном случае положим л 5 = 5. Если замыкание множества М относительно л полугрупповой операции совпадает с 5~, говорят, что М есть систем а образующих для 5. ш. и з|в ЗАМЕШАЕМОСТЬ 1 Пп.и СВОВОДНЫЕ ПОЛУГРУППЫ з1т Для произвольного алфавита (словаря) У множество У' является, Очевидно, полугруппой относительно опе- " рации конкатенации с системой образующих У; цепоч. ка Л является единицей этой полугруппы. Такая полу группа называется с в о б о д н о й.
Отображение ср полугруппы 5 в полугруппу 5' назы-, вается гомоморфным, если ч1х, я ~5[Ч1(ху)= '-, =Ч1(х)1Г(у)[. (Для случая, когда 5 и 5' — свободные полу группы, понятие гомоморфного отображения фактически ' было уже определено в $ !.1.) Взаимно однозначное го- .
моморфное отображение называется и з о м О р ф н ы м. Если ф — изоморфное отображение полугруппы 5 на по. лугруппу 5', то обратное отображение Ч '. 5'- 5 также является изоморфным. В этом случае говорят, что 5 и . 5' ивом о рф н ы между собой. Отношение эквивалентности /г на полугруппе 5 ;, называется к о н г р у э н ц и е й, если имеет место Чх, у, х', у'ее5[х/сх'ауйу':э ху/(х'у'[. Если /г — " конгруэнция на полугруппе 5, то любым двум классам Х, У я5Я однозначно отвечает класс, который мы будем обозначать ХУ, состоящий из всевозможных произведений ху, где х ~ Х, у ~ У.
Легко убедиться, что определенная таким образом иа 5/Р бинарная операция ассоциативна, т. е. 5Я является относительно этой операции полугруппой; эта полугруппа называется факторполугруппой полугруппы 5 по конгруэнции /г. Отображение полугруппы 5 на полугруппу 5Я, сопоставляющее каждому элементу 5 содержащии его класс, является, очевидно, гомоморфным — это так называемый естественный го м о морф из м. Пусть У вЂ” алфавит и р — произвольное отношение эквивалентности на У. Определим отношение р' на свободной полугруппе У' следующим образом: хр'у означает, что либо х =у =Л, либо х = а, ... аь, э = Ь1 ...
ЬА, где а1, Ь1~ У и а,рЬ1 (1'=1, ..., Ь). Ясно, что р" есть конгруэнция. Естественный гомоморфизм полугруппы У' на полугруппу У'/р" мы обозначим через 1р. Пусть теперь Х вЂ” произвольный класс по конгруэнции р* и х — произвольная цепочка, принадлежащая Х. Если ЛФХ, т. е. х=а, ... аы где а„..., а,ееУ, й) 1, мы обозначим цепочку 1р(а,) ... 1р(аь) (не зависящую, в силу определения конгруэнции р', от выбора цепочки х ее Х) через ф(Х). Если же Л ее Х(тогда Х = (Л) ) положим Ф(Х)=Л.
Мы получили, таким образом, отображение полугруппы У'/р* в свободную полугруппу (У/р)' с системой образующих У/р. Из способа определения этого отображения ясно, что оно гомоморфно; очевидно также, что каждая цепочка из (У/р)' имеет при отображении ф прообраз, и притом единственный. Таким образом, ф есть изоморфное отображение У'/р' на (У/р)"; следовательно, отображение О =1рф, сопоставляющее каждой непустой цепочке а, ... аА, где а„..., аА ее У, цепочку 1р(а,) ...
1р(аь) и единице полу- группы У' — единицу полугруппы (У/р)*, есть гомоморфное отображение У' на (У/р)*; мы будем называть его ал фа вити ы м гом о мор ф и з м о м. Если Я, и Я, — два отношения эквивалентности на произвольном множестве М такие, что каждый Я,-класс содержится в некотором Я;классе, мы будем называть Я, укрупнением ЯО Пусть р, — отношение эквивалентности на словаре У и рз — укрупнение рп тогда, как легко убедиться, р' будет укрупнением рг Определим на У/р, отношение эквивалентности ра, полагая АраВ тогда и только тогда, когда А и  — р,-классы, содержащиеся в одном и том же р1-классе.
Обозначим через ОО О, и в„алфавитные гомоморфизмы У' на (У/р,)", У' на (У/р,)' и (У/р,)* на ((У/р,)/ра)' соответственно. Определим далее гомоморфное отображение ((У/р1)/р11)*-> (У/р,)', полагая Ь11(а) для каждого рнгкласса а равным объединению всех р,-классов, принадлежащих а. Поскольку таким образом между (У/р1)(рэ и У/рм устанавливается взаимно однозначное соответствие, Ь11 есть изоморфное отображение ((У(р,)/ра)' на (У/р,)'. Поэтому, полагая 11„= 811ь1м получаем гомоморфное отображение (У/р,)* на (У/рз)'; это отображение сопоставляет каждой цепочке а, ... аА, где а„..., аА ~ У/р„ цепочку й1, йА, где [1„..., рь еи У/рз, такую, что а, с= в„..., аь ~рь. Ясно также, что 01П11=61.
Отображение 1111 мы также будем называть алфавитным г о м о м о р ф и з м о м. (Понятие, рассматривавшееся до сих пор под этим названием, становится частным случаем только что введенного, если заменить У на У/=, где — отношение тождества.) в ПП4 ЗАМЕШАЕМОСть И ВЗАИмозАМеШАЕМость з)й З)В ЕАмещАемость )п. 1 й П11.2. Замещаемость и взаимозамещаемость. Конфигурации Пусть У вЂ” произвольный словарь„ Š— язык в ело' варе 1' и х, уееУ". Будем говорить, что цепочка замешаема на цепочку у относительно сл в а р я у и я з ы к а Ь, и писать х ~ у, если вги, о~у* [ихо у,с вне:э иуо яЦ»). Если каждая из цепочек х, узамеща ма на другую относительно У и 1., говорим, что х и в з а и м о з а м е щ а е м ы о т н о с н'т е л ь н о 1' и пишем хбфу.
(Буквы У и Е будут опускаться, если нед у,с РазУмение невозможно.) Запись гпх(У, Л) бУдет означа (у)х~у), запись гй(У, ь) будет означать ((х, у) [х=)ву аналогично, с заменой =Р на (Ф, определим Ч"„(У, Ь и хр(У, Б). При невозможности недоразумения буква в этих обозначениях будет опускаться. Легко убедиться, что для произвольного языка в произвольном словаре У отношение Е4 является ко ' груэнцией на свободной полугруппе У*. Будем говорить, что отношение эквивалентности на свободной полугруппе У' с о г л а с о в а н о с языка 1. «: — У', если для любых двух цепочек х, у ~У' из х еи и хЯу следует у ееЬ.
Лемма ПП. 1. Отношение 4Ф согласовано с яз У,с ком Е и является укрупнением любой конгрузнции на У согласованной с Ь. Доказательство. Согласованность 4ф с Е н ' посредственно вытекает из определений. Пусть Я вЂ” ко груэнция на У', согласованная с Ь, х, у ~У' и хЯу Тогда для любых г, иди У* будет ххиЯгуи, и поэтом ххиееЕ влечет хуиее(.) таким образом, х=~у.
Лнало юь ') Ясно, что если Ьауо Ь~:-Ух, х, у~иум х, угмух, т х='Уу равносильно х=)«у. Однако обозначение 4в удобно в слу Уч Е у» г юь чаях, когда отношение рассматривается «в делом», кек миож ство пар. гично имеем у~х. Итак, всякий Я-класс содержится у, г. в некотором бф-классе. Лемма П11. 1 позволяет утверждать, что среди всех конгруэнций на У', согласованных с 1., отношение ЕФ имеет наименьший индекс. 3', с Лингвистический смысл понятия взаимозамещаемости состоит приблизительно в следующем.
Если интерпретировать У как множество ЛЗ-сегментов ') некоторого естественного языка и 1. — как множество грамматически правильных фраз этого языка, то взаимо- замещаемые цепочки будут представлять собой «синтаксически эквивалентные», т.
е. выполняющие одни и те же синтаксические функции, словосочетания. Так, в русском языке цепочку высокому дому можно, видимо, считать взаимозамещаемой с цепочкой умному совету, стене — с доске, исключительно важными — с важными Пусть теперь а ее У, х ее УУ+ (так что [х[ > 1) и ае4х. )У(ы будем говорить в этом случае, что х есть конфигурация 1-го ранга языка Е с результирующим а. При указанной выше лингвистической интерпретации словаря У и языка 1.
конфигурации 1-го ранга будут «потенциальными составляющими», т. е. цепочками, которые м о г у т входить в лингвистически естественные системы составляющих грамматически правильных предложений данного языка. Так, в русском языке цепочка исключительно важными является, видимо, конфигурацией 1-го ранга с результирующим важными (а также с любым из результирующих ценными, вредными, скверными, ...); существуют, очевидно, правильные русские предложения, для которых эта цепочка входит в число «естественных» составляющих [например, (Эти работы) (являются (исключительно важными))], Однако «потенциальные составляющие» заведомо не исчерпываются конфигурациями 1-го ранга.
Например, словосочетание важньчми работами является «потенциальной составляющей» [ср. Я (((не был) знаком) ((с (важными работами)) Иванова ))); в то же время ') Ср., впрочем, своску *) иа стр. 327. 1 пп.21 злмещлемость 11 излимозАлте!цлемость З21 зймещАемость 1п. и ясно, что на это словосочетание могут быть замещаемы только такие цепочки, как работами, лекциями, шапками, докладами, собаками, ушами*) и т. п., и поэтому,' если бы цепочка важными работами была конфигура-:„' цией 1-го ранга, то только с такими результирующими. '" Но, например, в фразе Я не был знаком с исключительно важными работами Иванова нельзя без нарушения грамматической правильности заменить важными рабо- ',„ тами ни на работами, ни на лекциями, ни на собаками;;.1 ушами и т, п. Такая замена возможна лишь в тех кон-; текстах, где нет словосочетаний вроде исключительно: важными или невероятно важными, перекрывающихся с заменяемым вхождением словосочетания важными ра-; ботами.
Эти соображения приводят к следующему опре- ' делению. Пусть г ) 1 — натуральное число, и для каждого 1,; 1 ( 1 ( г, определено понятие конфигурации ранга языка Е. Тогда цепочка х еи )г(геназывается кон ф и гу-;, рацией ранга г языка 1. с результирующим а, где а ее )г, если выполняются следующие два условия:: 1) а =)2 х; 2) если г,хгг ен Е и цепочка г,хг, не содержит.' вхождений конфигураций рангов, меньших г, перекры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
