Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Для полугрупп с единицей положение оказывается более сложным: здесь, вообще говоря, восстановить гомоморфизм по одному классу канонической конгруэнции невозможно.
Ничто не мешает, впрочем, и здесь называть ядром гомоморфизма тот класс, к которому принадлежит единичный элемент исходной полугруппы. В рамках интересующей нас проблематики понятие ядра гомоморфизма занимает важное место (хотя и не столь важное, как в теории групп); в дальнейшем мы будем неоднократно пользоваться им.
Более или менее существенная роль ядра в том или ином конкретном случае зависит от роли единичного элемента в полугруппе образов, т. е. в конечном счете решающая роль принадлежит образам.
§ 13.2. КОНГРУЭНЦИЯ и ЭКВИВАЛЕНТНОСТИ,
сопоставляемые языку
ІЗ.2.1. Конгруэнция по допустимым контекстам (взаимозамещаемость )
Пусть Я — алфавит, %* — свободная полугруппа над 91, Z-сЯ*— язык и Мєїї* — некоторая цепочка. Если существуют цепочки, 208
Часть III. Алгебраический подход
А, В е Я*, такие, что AMB є L, мы будем называть упорядоченную пару (А, В) допустимым контекстом цепочки M относительно L.
Примеры. Пусть Я = {а, Ь, с), ! — «зеркальный язык» [ХсХ\Х є [а, &}*}. Для цепочки ас пара (b, ab) есть допустимый контекст относительно L. Множество допустимых контекстов для ас состоит из всех пар вида (X, аХ).
Для цепочки аса множество допустимых контекстов есть {X, Х\Х <= {а, &}*}; оно содержит, в частности, пару (?,?), где ? — пустая цепочка.
Для цепочки accb нет ни одного допустимого контекста относительно L, т. е. множество допустимых контекстов этой цепочки пусто.
N3: заметим, что если множество допустимых контекстов включает «пустой контекст», т. е. пару (?,?), то тем самым оно само не пусто!
Определим на свободной полугруппе Я* отношение =L следующим образом. Будем писать
M^1P1
если множество допустимых контекстов цепочки M относительно языка L совпадает с множеством допустимых контекстов цепочки P относительно того же языка.
Другими словами, =L означает, что
—1 либо ни для М, ни для P нет допустимых контекстов относительно L;
— либо и для М, и для P имеются допустимые контексты относительно L, причем всякая пара, являющаяся допустимым контекстом для М, является допустимым контекстом и для Р, и наоборот.
В более компактной форме это утверждение записывается так:
[MbslP]&(VXє Г)(VY є Г)[XMY єЩXPY є= L). Отношение =L называется взаимозамещаемостью относительно L.
Пример. Если Я = [а, Ь] и L — конечный язык [aaa, aba}, то aaa^sLdba, причем соответствующее множество допустимых контекстов есть {(?,?)}, и bab = Lbob, причем соответствующее множество допустимых контекстов пусто.
Ясно, что есть отношение эквивалентности. Посмотрим, как оно ведет себя относительно конкатенации.
Пусть А и В — произвольные цепочки и P SSlM-, сравним цепочки AMB и АРВ. Любому контексту (X, Y), независимо от того, является ли он допустимым для M и Р, можно сопоставить контекст (XAtBY). Тогда мы будем иметь
X (AMB)Y єе L фф (XA) M (BY) є L (XA) P (BY) є= L
^X(APB)Y eL Г л XIII Г омоморфизм полугрупп
209
Таким образом, всякий контекст, допустимый для АМВ, является допустимым и для АРВ\ ясно, что обратное также верно. Поэтому
P = LM^>APB = LAMB.
Следовательно, отношение =L (взаимозамещаемость) является конгруэнцией. Мы будем называть его еще конгруэнцией по допустимым контекстам относительно L.
Пример.
Я = {а, Ь}\ L = {ambnap \ m, п > 1, р > 0}.
Цепочки, не принадлежащие L, либо имеют вид ат, либо имеют начальный сегмент вида bT, г ^ 1, или вида ambnavbr, m, п, р, г 1.
Все эти цепочки принадлежат одному классу, который соответствует пустому множеству допустимых контекстов.
Цепочки языка L распределяются по двум классам: класс цепочек вида ambn, имеющих допустимые контексты вида (,ах, bvaz\x, у, z> 0), и класс цепочек вида ambnaP, 1, имеющих допустимые контексты вида (ax,az). Таким образом, L есть объединение этих двух классов.
Отношение =ь задает разбиение множества її* на непересекающиеся классы и определяет фактормножество Я*/=х,, являющееся полугруппой (с единицей) относительно операции, индуцированной конкатенацией.
Если Af є L и M =lP, то контекст (Е,Е), допустимый для М, является допустимым и для Р, откуда P^L. Если L содержит AJ, то L содержит и весь класс цепочек, находящихся с M в отношении = L-
Теорема. Язык L может быть представлен как объединение некоторых классов взаимозамещаемых цепочек.
Ср. предыдущий пример.
13.2.2. Основное свойство взаимозамещаемости
Докажем следующую теорему.
Теорема. Всякая конгруэнция, определенная на її* и такая, что L является объединением некоторых ее классов, либо тоньше1), чем конгруэнция =l, либо совпадает с =ь-
Пусть СЇ —такая конгруэнция. Покажем, что из АШВ следует AsslB. В самом деле,
[АШ & XAY [X AYfStXBY & XAY є L};
а поскольку язык L есть объединение Сї-классов, он содержит XBY, если только он содержит XAY.
') Эквивалентность тоньше эквивалентности если всякий ~і-класс ^Держится в некотором ~2-классе, и при этом и ~2 не совпадают,— 11Pum ред. 210
