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

Действительно, мы можем рассматривать граф состояния как разбиение ∑* на множества слов. Каждое множество соответствует одному из состояний и является в точности множеством слов, образующих путь, который выходит из начального состояния и заканчивается в заданном состоянии. Рабин и Скотт дали математическую характеристику таких множеств, а именно: они являются множествами эквивалентности правоинвариантного отношение эквивалентности; отношение эквивалентности rel (сокращенно от relation (англ.) — отношение) над множеством слов называется правоинвариантным, если из соотношение W rel W′ вытекает, что WU rel W'U. Рассматривая очевидное аналогичное определение левоинвариантного отношение, Рабин и Скотт определили отношение конгруэнтности как отношение эквивалентности, которое левоинвариантно и правоинвариантно.

3. Теорема. Если γ - гомоморфизм и γ-1γ (Е) = Е, то моноид

М=γ(∑*) может быть гомоморфно отображен на синтаксический моноид S (Е).

Доказательство. Напомним, что элементами S(Е) есть множества конгруэнтности слов по модулю Е. По теореме 2 каждое множество конгруэнтности по модулю γ будет подмножеством некоторого множества конгруэнтности по модулю Е. Пусть η — такое отображение моноида М на S(Е), что для каждого s M η(s) есть такое множество конгруэнтности по модулю Е, подмножеством которого будет γ-1(s) (множество конгруэнтности по модулю γ). Очевидно, что η отображает М на S(Е). Нам необходимо только доказать, что η представляет собой гомоморфизм, т. е. что для каждых элементов s1, s2 M η(s1s2) =η(s1)η(s2). Но так как каждый элемент из М является образом при гомоморфизме γ некоторого слова из ∑*, достаточно показать, что для всех слов W1 и W2

η [γ(W1) γ(W2)]=η [γ(W1)]η [γ(W2)]. (*)

Так как γ — гомоморфизм, γ (W1W2) = γ (W1) γ (W2), поэтому для проверки справедливости соотношения (*) достаточно доказать, что

η [γ(W1W2)]=η [γ(W1)]η [γ(W2)]. (**)

или, другими словами, надо доказать, что отображение ηγ есть гомоморфизм.

Но ηγ отображает каждое слово в его множество конгруэнтности. Читатель может без труда установить это, рассмотрев определение

отображения γ. То, что это отображение есть гомоморфизм, было уже показано при обсуждении построения синтаксического моноида события.

Все изложенное справедливо независимо от того, конечен или бесконечен моноид γ(∑*). Здесь нас интересуют только регулярные события, и последующие теоремы подскажут нам, что можно ограничиться рассмотрением только таких γ, для которых моноид γ(∑*) конечен.

Конечный граф состояния над алфавитом ∑ имеет конечное число вершин или состояний, обозначенных окружностями. Из каждого кружочка выходит стрелка, соответствующая каждой букве из ∑, наконечник стрелки достигает некоторого состояния. Одно состояние избрано в качестве начального, другие могут быть названы терминальными состояниями. На рис. 3.16 ∑={0, 1} и имеется три состояния.

Рис. 3.16

Терминальные состояния — это двойные окружности, и единственная, никак не обозначенная точка указывает начальное состояние. Такой граф можно рассматривать как граф, соответствующий отображению переходов конечного автомата с входным алфавитом ∑.

В таком графе G пусть G (s, W) обозначает состояние — конечную точку пути, начинающегося в s и прочитывающего слово W. Состояние G (s, W) существует и однозначно определено в графе состояния. Пусть G (W) обозначает состояние G (s0, W), где s0 — начальное состояние. Так, G (λ) есть само начальное состояние. Мы полагаем, что использование буквы G для обозначения графа и описанной функциональной зависимости не вызовет путаницы.

Говорят, что событие Е, содержщееся в ∑*, является регулярным событием, если существует конечный граф состояний G с начальным состоянием s0 и множество терминальных состояний, такие, что

E = {W ∑*|G(W) Т}.

Известно, что регулярные события — это в точности те события, которые можно получить с помощью регулярных выражений, последние представляют события через конечное число операций об′единения, умножения (А• В={ab|а А й b В}) и операции итерации (А*={a1.. ап|п≥0 каждое а А}).

Приведенным (или редуцированным) графом состояния G для peлярного события Е называется граф, в котором:

1) для каждого состояния s из G существует слово W, такое, что s=G(W),

2) для каждой пары состояний s и s', где s≠s', существует W, такое, что или G (s, W)— терминальное состояние, a G(s', W) — нетерминальное, или наоборот.

4. Теорема. Каждому регулярному событию Е соответствует единственный с точностью до изоморфизма приведенный граф состояний, имеющий меньше состояний, чем любой другой граф для Е, и вычисляющийся алгоритмически одним из обычных способов, если
событие задано (как, например, произвольный граф состояний или
регулятное выражение).

Даказывать эту теорему не будем.

5. Теорема. Два слова W и W′ содержатся в одном и том же множестве конгруэнтности по модулю регулярного события Е тогда и
только тогда, когда для каждого состояния приведенного графа состояния события Е справедливо равенство G(s, W)=G(s, W′).

Доказательство. Предположим сперва, что W и W′ приналежат одному и тому же множеству конгруэнтности по модулю Е, т. е. для всех слов V и X VWX Е тогда и только тогда, когда VW' E. Пусть s - любое состояние. Существует путь из начального состояния в s, пусть этот путь прочитывает (или расшифровывает) слово V. Предположим, что s0=G(s, W)≠G(s, W)=sv. Тогда существует такое X, что или G(s0, X) является терминальным состоянием и G(s1,X) не является терминальным состоянием, или наоборот. Тогда VWX Е, но VW' E, или наоборот. Но эти соотношения противоречат допущению, что W≡W′(mod Е). Из этого следует, что G (s, W)=G(s, W′).

Предположим теперь, что для каждого s из G выполняется равенство G (s, W)=G (s, W′). Тогда для каждого слова V

G(VW)=G(VW′) и, следовательно, для каждого слова X G(VWХ)=G(VW′X).Поэтому мы получаем, что VWX E тогда и только тогда когда VW' Е.

Если задан граф G и выбрано слово W, то имеется отображение на множестве состояний графа G, переводящее состояние s в G (s, W).
Тогда из теоремы 5 следует, что конгруэнтными по модулю Е будут такие слова, которые индуцируют одинаковые функции на приведенном графе состояния G события Е. Заметим, что если G имеет п состояний, то существуют самое больше пп отображений на множестве состояний графа G. Вспомнив теперь теорему 3, мы получаем следующий важный результат.

Следствие. Событие Е на алфавите ∑ регулярно тогда и только тогда, когда синтаксический моноид S(Е) конечен, и, следовательно, Е регулярно тогда и только тогда, когда существует гомоморфизм моноида ∑* на конечный моноид S, такой, что Е =γ-1γ(S).

Теорема 5 дает нам удобный вычислительный метод для получения синтаксического моноида; приведем соответствующий пример. Рассмотрим граф G, изображенный на рис. 3.16. Очевидно, что G приведенный. Для того чтобы следить за множествами конгруэнтности слов, мы должны знать, что происходит при выборе произвольного слова и произвольного состояния. Построим новый граф состояния G', начальное состояние которого обозначено как qrs, и такой, что для каждого слова W G'(W)=G (q, W)G (r, W)G(s, W). Граф G' строится последовательно шаг за шагом, а именно G'(0) = qqr, G' (1) =rss,G'(00) = qqq, G'(01) =rrs и т. д. Результат представлен на рис. 3.17.

Рис. 3.17

Каждое состояние графа G' представляет множество конгруэнтныx слов события, которое задается графом G. Для любого состояния соответствующее множество конруэнтности есть множество всех таких слов W, что G'(W)=s'. Следовательно, множество, соответствующее состоянию qrs, состоит из пустого слова λ, состоянию qqr соответствует множество 0 (10)* и т. д. Из метода построения и теоремы 5 очевидно следует, что G'(W)=G'(W')тогда и только тогда, когда W=W'(modЕ). Следовательно, G' представляет синтаксический моноид графа G. Если слова — представители множества конгруэнтности будут по соглашению именовать классы (за исключением т для rrr), то таблица умножения этого моноида будет иметь следующий вид:

Эту таблицу умножения можно отождествить с самим моноидом,
Отметим, что любая небольшая полугруппа может быть практически
преставлена в таком виде. Отметим также, что граф состояния на
рис. 3.17 включает в себя такую же информацию; умножение любых двух элементов может быть получено на рисунке почти так же легко, как и с помощью таблицы. Например, если требуется найти произ­ведение элемента (10) с (т), мы заметим, что т = 110 и затем выведем 10110 из начального состояния и приведем к окружности, обозначен­ной как rrr. Теперь мы вспомним, что rrr представляет 110=т, и получим результат умножения. Для того чтобы сделать этот процесс более ясным, заменим граф состояния, изображенный на рис. 3.17, гра­фом, представленным на рис. 3.18, который станем называть моноидным графом.