Дискретно-непрерывная математика (стр. 110 )

Скажем несколько слов об обозначениях. Пусть γ — такое отображение, что для любого слова W ∑* γ(W) будет элементом моноида М. Говорят, что отображение γ есть гомоморфизм, если для всех слов W и V ∑* выполняется соотношение γ(WV) = γ(W)γ(V). Для любого множества А слов из ∑* γ(А) есть в точности множество всех таких элементов т из М, что для некоторого слова WА имеем γ(W)=т. γ-1(т) есть множество всех слов, которые переходят в т при отображении γ. И для любого подмножества S моноида М γ-1(S) есть в точности такое множество слов из ∑ *, которые переводятся в элементы множества S отображением γ.

Заметим, что если γ — гомоморфизм моноида ∑* на некоторый моноид, то необходимо γ(λ)=е. Так как пустое слово λ играет большую роль в наших рассмотрениях, существенно, чтобы любая применявшаяся полугруппа была моноидом. Разумеется, теория регулярных событий могла бы быть развита без специального упоминания пустого слова, но включение этого слова делает все результаты более естественными. По этой причине удобно при изучении событий исключить из рассмотрения те полугруппы, которые не является моноидами.

Обычно, если имеется некоторое событие Е, мы интересуемся только теми гомоморфизмами γ, для которых Е замкнуто относительно γ-1γ, т. е. такими гомоморфизмами γ, что Е = γ-1γ(E).

Для любого отображения γ моноида ∑* назовем слово W1 конгруэнтным слову W2 no модулю γ [или W1 ≡ W2 (mod γ)], если

γ(W1) =γ(W2). Будем также говорить, что W1 конгруэнтно W2 по модулю Е [или W1 ≡ W2 (mod E)], если для любых слов V и X VW1X Е тогда и только тогда, когда VW2X Э. Читатель должен четко понимать, что это есть два различных вида конгруэнтности. Но хотя они и различны, существующая между ними связь, определяет появление моноидов в изучении событий.

Мы используем разбиение ∑* на конгруэнтные множества и укажем зависимость между этими разбиениями для раздичных отношений конгруэнтности. Множеством конгруэнтных слов (по модулю γ или по модулю Е) называется непустое множество, которое содержит вместе с некоторым элементом все те и только те слова, которые конгруэнтны этому элементу. Множества конгруэнтности (множества конгруэнтных слов) чаще называются классами конгруэнтности, но мы предпочитаем употреблять термин «множество» для обозначения множества слов, а термин «класс» — для класса множеств.

Среди всех гомоморфних отображений моноида ∑* существует одно наиболее важное для изучение события Е, а именно отображение в синтаксический моноид события Е или в S (Е). Элементами моноида S(Е) являются множества конгруэнтности по модулю Е. Гомоморфизм просто отображает слово из ∑* на множестве конгруэнтности по модулю Е, какое это слово содержит. Отображение определено корректно, поскольку каждое слово над алфавитом ∑ принадлежит одному и только одному множеству конгруэнтности по модулю Е.

Для того чтобы сделать множество S(Е) моноидом, мы должны ввести операцию умножения и установить ее ассоциативность. Для этого заметим, что если А и В — множества конгруэнтности, то для некоторого множества конгруэнтности С АВ С, т. е. множество конгруэнтности С содержит все слова вида WW', где W A и W' B. (Однако ввиду того, что в С могут быть слова, не представляемые в таком виде, мы не можем в общем случае утверждать, что С=АВ.) Это замечание дает нам операцию умножения, а именно, произведением двух множеств конгруэнтности А и В называется такое множество конгруэнтности С, что АВ С. Ассоциативность этой операции немедленно следует из ассоциативности умножения слов в ∑*. (Фактически это указывает, как следует проверять последнее предложение. Несколько сложнее доказывается корректность введенной операции умножения. Здесь надо установить, что все слова из АВ содержатся в одном и только в одном множестве конгруэнтности).

Название «синтаксический моноид» вызвано тем, что его определение дается в сроках понятия конгруэнтности слов по модулю события.

1. Теорема. Если γ есть гомоморфизм ∑* в S (Е), то Е замкнуто относительно γ -1γ , более того, для любых слов W и W' W ≡ W' (mod γ) тогда и только тогда, когда W≡W' (mod E).

Доказательство. Для того чтобы установить первое утверждение, достаточно доказать, что любые два слова W и W', отображающиеся при гомоморфизме γ в один и тот же элемент, или оба принадлежат Е, или оба находятся вне Е. Но если W и W' отображаются в один и тот же элемент, они должны быть конгруэнтны по модулю Е, следовательно, W =λWλЕ тогда и только тогда, когда W′ =λW′λЕ. Второе утверждение теоремы 1 представляет собой просто переформулировку определения синтаксического моноида.

Однако существуют и другие гомоморфизмы γ моноида ∑*, при которых событие Е замкнуто относительно γ-1γ. Связь между моноидами, являющимися образами этих гомоморфизмов и синтаксическим моноидом, исключительно важна. Следующий результат представляет собой обобщение теоремы 1.

2. Теорема. Для того чтобы событие Е было замкнуто относительно γ -1γ, где γ — гомоморфизм, необходимо и достаточно, чтобы для всех слов W и W' из соотношения W≡W' (mod γ) следовало W≡W' (mod E).

Доказательство. Достаточность. Предположим, что условие выполнено. Пусть для любого слова W ∑* AW обозначает множество слов, конгруэнтных W по модулю γ. Тогда для любого W γ-1γ(AW)=AW. Из этого следует, что для В = AW γ -1γ (В) =В. Требуемое равенство γ -1 [γ (Е)] = Е будет доказано, если мы покажем, что Е = В. Перейдем к проверке последнего равенства.

Включение Е В немедленно следует из определения множества В. Предположим теперь, что W — произвольное слово из В. Существует слово W'E, такое, что W′ ≡W (mod γ), тогда по условию W′ ≡W(modЕ). Следовательно, W также принадлежит Е (действительно, W′=λW′λE, откуда по определению конгруэнтности следует, что λWλ = W E).

Необходимость. Предположим, что γ -1 [γ (Е)] = Е. Необходимо доказать, что если слова W и W′ удовлетворяют соотношению W≡W′ (mod γ), то W≡W′ (mod Е). Предположим, что W ≡ W′ (mod γ). Это значит, что γ (W) ≡ γ (W'). Для того чтобы показать, что W ≡ W′ (mod Е), мы должны проверить, что для всех V и X VWX E тогда и только тогда, когда VW' E. Но заметим, что γ(VWX) =γ(V)γ(W)γ(X) и γ(VW′X)=γ(V)γ(W′)γ(Х), так как отображение γ есть гомоморфизм; поскольку γ(W) = γ (W'), то γ(VWX)=γ(VW'). Из этого следует, что VWX γ-1[γ (VW')] и VW' γ -1[γ (VWX)]. Так как γ-1 [γ(Е)]=Е, то VWX E тогда и только тогда, когда VW′XЕ. Теорема доказана полностью.

Подумаем о значении теоремы 2. Гомоморфизм и событие Е определяют разбиение моноїда ∑* на множества конгруэнтности. Теорема 2 утверждает, что для замкнутости Е относительно γ-1γ необходимо и достаточно, чтобы разбиение, определяемое гомоморфизмом γ, было мельче (или равно) разбиения, определяемого событием Е. Другими словами, необходимо и достаточно, чтобы каждое множество конгруэнтности по модулю γ было подмножеством некоторого множества конгруэнтности по модулю Е. Таким образом, разбиение, соответствующее гомоморфизму на синтаксический моноид, самае грубое среди всех разбиений, соответствующих гомоморфизмам γ, таким, что γ-1γ(Е)=Е. Теорема 3 устанавливает фундаментальное отношение между моноидами, являющимися образами таких гомоморфизмов, и синтаксическим моноидом. Читателя, возможно, заинтересует сравнительная роль синтаксического моноида в классе всех моноидов, для которых γ-1γ(Е)=Е (где γ — гомоморфизм на соответствующий моноид), и роль (редуцированного) приведенного графа состояния в классе графов состояния для данного события. Как известно, произвольный граф состояния для события гомоморфен приведенному графу состояния.