Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ пил
СВОБОДНЫЕ ПОЛУГРУППЫ
315
С другой стороны, опираясь лишь на понятие сегмента, относящееся целиком к внешней стороне языка, можно рассчитывать получить лишь довольно «бедные» модели (ср. ниже, стр. 327). Поэтому представляется целесообразным включить в число исходных данных лексические значения слов. Для этого мы введем понятие лексически значимого сегмента (ЛЗ-сег-мента), промежуточное между понятиями сегмента и словоформы; именно, ЛЗ-сегмент — это сегмент, снабженный лексически значением (но не грамматическими). Например, в предложении Он говорит только о физике, читает книги только по физике, и о нем говорят только как о физике первые два вхождения сегмента физике являются вхождениями одного и того же ЛЗ-сег* мента — но разных словоформ! — а третье отвечает другому ЛЗ-сегменту. В дальнейшем мы будем понимать элементарные символы как ЛЗ-сегменты. Впрочем, до некоторого момента будет допустимо также и понимание их как сегментов; место, начиная с которого введение лексических значений существенно, будет явно ука* зано (стр. 327—328).
§ П11.1. Свободные полугруппы
Этот параграф вспомогательный; в нем излагаются некоторые простые алгебраические понятия, которые понадобятся нам в дальнейшем.
Множество с определенной на нем ассоциативной бинарной операцией называется полугруппой. Для обозначения полугрупповой операции обычно используется мультипликативная запись: результат операции над элементами х и у (в этом порядке) обозначается ху. Элемент е полугруппы 5 называется единицей, если для любого xg5 имеет место хе — ех = х. Легко видеть, что если полугруппа содержит единицу (что не обязательно), то только одну. Пусть 5 — полугруппа и Ms5; если 5 обладает единицей е, обозначим через 5Л множество 5 — {е}; в противном случае положим 5Л = S. Если замыкание множества М относительно полугрупповой операции совпадает с 5Л, говорят, что М есть система образующих для 5.
316
ЗАМЕЩАЕМОСТЬ
[П. II
Для произвольного алфавита (словаря) V множество V* является, очевидно, полугруппой относительно операции конкатенации с системой образующих V; цепочка Л является единицей этой полугруппы. Такая полу* группа называется свободной.
Отображение ф полугруппы 5 в полугруппу S' называется гомоморфным, если Vx, у е 5 [ф (ху) = = ф(х)ф(г/)]. (Для случая, когда 5 и S'— свободные полу-* группы, понятие гомоморфного отображения фактически было уже определено в § 1.1.) Взаимно однозначное гомоморфное отображение называется изоморфным. Если ф — изоморфное отображение полугруппы 5 на полугруппу S', то обратное отображение ф-1: S'~*S также является изоморфным. В этом случае говорят, что 5 и S' изоморфны между собой.
Отношение эквивалентности R на полугруппе 5 называется конгруэнцией, если имеет место Vx, у, х', у' ^ S[xRx' & yRy' zd xyRx'y']. Если R — конгруэнция на полугруппе S, то любым двум классам X, Y е S/R однозначно отвечает класс, который мы будем обозначать XY, состоящий из всевозможных произведений ху, где х е X, у е У. Легко убедиться, что определенная таким образом на S/R бинарная операция ассоциативна, т. е. S/R является относительно этой операции полугруппой; эта полугруппа называется фактор-полугруппой полугруппы 5 по конгруэнции R. Отображение полугруппы 5 на полугруппу S/R, сопоставляющее каждому элементу 5 содержащий его класс, является, очевидно, гомоморфным — это так называемый естественный гомоморфизм.
Пусть V — алфавит и р — произвольное отношение эквивалентности на V. Определим отношение р* на свободной полугруппе V* следующим образом: хр“у означает, что либо х = у = А, либо х = а{ ... ak, у = Ъх ... bk, где ait bt <= V и а{рЬ{ (i — 1, ..., к). Ясно, что р* есть конгруэнция. Естественный гомоморфизм полугруппы V* на полугруппу V*lp мы обозначим через ф.
Пусть теперь X — произвольный класс по конгруэнции р* и х — произвольная цепочка, принадлежащая X.
Если АфХ, т. е. x = ai...ak, где ...........ak<=V,
k^l, мы обозначим цепочку ф(О)) ... ф(ай) (не зависящую, в силу определения конгруэнции р\ от выбора
§ ПП.1]
СВОБОДНЫЕ ПОЛУГРУППЫ
317
цепочки х ^ X) через ф (X). Если же А е X (тогда X = {Л}). положим oJj(X) = A. Мы получили, таким образом, отображение полугруппы V*/p* в свободную полугруппу (V7p)* с системой образующих F/p. Из способа определения этого отображения ясно, что оно гомоморфно; очевидно также, что каждая цепочка из (F/p)* имеет при отображении -ф прообраз, и притом единственный. Таким образом, г|э есть изоморфное отображение V/p* на {VIр)*; следовательно, отображение 8 = фг1з, сопоставляющее каждой непустой цепочке ах ... ак, где аи a*eF, цепочку ф(а,) ... ф(ай) и единице полугруппы V* — единицу полугруппы (F/p)*, есть гомоморфное отображение V* на (F/p)*; мы будем называть его алфавитным гомоморфизмом.
Если Я, и Яг - два отношения эквивалентности на произвольном множестве М такие, что каждый ^,-класс содержится в некотором ^2-классе, мы будем называть укрупнением Пусть р! — отношение
эквивалентности на словаре V и р2 — укрупнение pj; тогда, как легко убедиться, р* будет укрупнением р*. Определим на V/p{ отношение эквивалентности р12, полагая Ар12В тогда и только тогда, когда А и В—ррклассы, содержащиеся в одном и том же р2-классе. Обозначим через 0,, 02 и 012 алфавитные гомоморфизмы V на (F/p^*, V* на (V/p2)* и (F/pi)* на ((К/р1)/р12)’ соответственно. Определим далее гомоморфное отображение ?t2: ((Wp,)/p>2r->(W, полагая ?12(а) для каждого р12-класса а равным объединению всех р^классов, принадлежащих а. Поскольку таким образом между (V/pl)/p2 и F/pI2 устанавливается взаимно однозначное соответствие, ti2 есть изоморфное отображение ((F/p,)/p12)’ на (F/p2)*. Поэтому, полагая т]12 = 012?12, получаем гомоморфное отображение (К/Pi)* на (F/p2)*; это отображение сопоставляет каждой цепочке ... ак, где а,, ..ak <= V/pu
