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

Рис. 3.18. Рис. 3.19

Мы будем рассматривать его как удобное представление син­таксического моноида регулярного события. Далее предполагается, что читатель знает, как из приведенного графа состояния строится моноидный граф и как он используется в качестве представления синтаксического моноида. (Следует отметить, что ряд специалистов по современной теории групп добились успехов в применении таких графов для представления групп.)

Рассмотрим еще два примера. На рис. 3.19а и 3.20а изображены приве­денные графы состояния двух событий, а на рис. 3.19б и 3.20б —соответст­вующие им синтаксические моноиды. Стрелки с двумя концами, по­меченные 1 (или 0), означают, что 1 (или 0) переходит из одного со­стояния в другое, и наоборот.

Рис. 3.20

Многие задачи о конечном автомате могут быть решены, если из­вестно, из каких подгрупп состоит синтаксический моноид автомата и какую роль в строении моноида играют его подгруппы. Читатель, знакомый с работами Крона и Роудза по теории декомпозиции, уже зна­ет, какое значение в декомпозиции имеют подгруппы моноида и его негрупповая часть, а также как они связаны друг с другом. В иссле­дованиях событий было открыто (результат следует из работы Щют-ценберже), что если синтаксический моноид события не имеет не­тривиальных подгрупп, то для события могут быть получены многие факты даже без применения алгебры. Например, такое событие пред­ставляется как разновидность регулярного события, выражаемая в терминах операций объединения, пересечения, дополнения (над множеством всех слов, порожденных алфавитом) и умножения, но без

использования итерационной операции (или звездочки*). Кроме того, как доказал Щютценберже, это в точности те события, которые могут быть описаны в некоторой системе символической логики. Из этого результата видно, какое большое значение имеют относительно замк­нутые системы символической логики. С 1962 г. (с появлением теории Крона и Роудза) все большее значение стали играть алгебраические достижения в теории автоматов. И здесь особое значение приобретает исследование группового строения автомата. Поэтому заключитель­ная часть данного пункта посвящается изложению алгоритма для нахождения максимальных подгрупп конечного моноида.

Подгруппой моноида называется подполугруппа, которая в свою оче­редь является группой. Другими словами, это множество элементов, кото­рое: 1) замкнуто относительно опе­рации произведения элементов, 2) со­держит единичный элемент, 3) вместе с любым принадлежащим ему элементом содержит обратный элемент. Еди­ничный элемент i подгруппы вовсе не обязан быть единицей основного моноида. Существенно то, что он должен удовлетворять соотношению i 2 = i, т. е. быть идемпотентом моноида. Наоборот, каждый идемпотент моноида является единицей некоторой подгруппы моноида, она может быть даже тривиальной группой (т. е. группой порядка 1), состоящей олько из самого идемпотента.

Если задана подгруппа G с единицей i, то мы будем говорить, что G будет подгруппой вокруг идемпотента i. Оказывается, что каждый идемпотент моноида имеет вокруг себя максимальную подгруппу, точный результат дается теоремой 11. Проблема, которой мы будем заниматься, состоит в нахождении этих максимальных подгрупп, так как все другие подгруппы моноида представляют собой подмножества (и, разумеется, подгруппы) максимальных подгрупп. Заметим, что в моноиде, изображенном на рис. 3.18, все элементы, кроме 0 и 1, являются идемпотентами. Моноид из рис. 3.20 имеет два идемпотента λ и 111, в то время как у моноида, приведенного на ри­сунке 3.19б, только один идемпотент λ — единица моноида. Мы увидим вскоре, что изобилие идемпотентов в примере, представленном на рис. 3.18, отражает тот факт, что моноид в этом случае имеет только три­виальные подгруппы. С другой стороны, моноид на рис. 3.19б является группой. Где-то между этими двумя крайними случаями находится моноид, изображенный на рис. 3.20б, он содержит нетривиальные под­группы, но в то же время не является группой. Для того чтобы у чи­тателя не возникло ложное впечатление, мы должны отметить, чю существуют моноиды, у которых мало идемпотентов, но которые имеют только тривиальные подгруппы. Пример такого моноида представлен на рис. 3.21.

Рис. 3.21

Этот моноид имеет только два идемпотента и не содержит (как мы увидим) нетривиальных подгрупп. (Мы предоставляем читателю проверить, что на рис. 3.21 изображен граф моноида. Один из методов проверки того, что граф состояния является графом моноида, заключается в том, чтобы представить его как приведенный граф со­стояния для события и построить для него граф синтаксического мо­ноида. Теперь первоначальный граф является графом моноида тогда и только тогда, когда он изоморфен графу, полученному в результате предложенного построения. Доказательство последнего утверждения

мы оставляем читателю в каче­стве самостоятельного упраж­нения.)

Каждый элемент а конечного моноида М определяет последо­вательность степеней а, а2, а3, ... Так как моноид М конечен, в этой последовательности степеней имеется только конечное число различных элементов. Пусть п (a), q (а) и т (а) — положительные целые числа, определяемые следующим образом: п (а) — наименьшее целое положительное число, такое, что для некоторого у>п(а), ап(а) = ау; затем q (а) есть наименьшее целое положительное число, такое, что ап(а) =an(a)+q(a), наконец, т (а) есть такое кратное q (а), что п(а) ≤т(а)≤г(а)+ q (a) — 1. Три построенных целых числа определяют степени элемента а, играющие исключительно важную роль в нахожде­нии максимальных подгрупп моноида. Докажем некоторые результаты для этих чисел.

Лемма. Элементы ап(а), ап (а)+1 ,…,ап(а)+q(а)-1 попарно различны.

Доказательство. Предположим, что aп(a)+l = aп(a)+j, 0 ≤ i<j ≤q(а)-1. Так как из равенства ах = ау следует, что для любого z ax+z = aу+z, мы получаем соотношение ап(а)+і+q(а)-1=ап(а)+q(а)=ап(а), которое противоречит определению числа q (а),так как i + q (а) — j <q(а).

7. Теорема. Элемент am(a) есть идемпотентом и это единственный идемпотент среди степеней а.

Доказательство. Заметим, что из равенства ап(а)=ап(а)+q(а)
следует, что для всех х≥п(а)

ах= ах+q(а) (***)

Так как т(а) есть кратное числа q(a), то

ат(a)=ат(а)+q(а)=ат(а)+2q(а)=…=а2т(a)

Это доказывает, что элемент ат(а) является идемпотентом.

Предположим теперь, что ах также идемпотент, т. е. что а2х= ах. Число х не может быть меньше, чем п(а), так как ап(а) есть по
определению наименьшая степень элемента а, равная большей степени
того же элемента. Предположим, что х-п(а)≡i1[mod q(а)] и

2х — п (а) ≡ i 2 [mod q (а)], где 0 ≤ i 1 ≤q (а) — 1 и 0 ≤ i2 ≤ q (а) — 1.
В силу равенства (***) ах = ап(а)+ и а2х=ап(а)+. В силу леммы ах и а2х будут равны, только если числа i1 и i 2 равны, откуда
следует, что х=2х[mod q(а)]. Это последнее соотношение
справедливо только тогда, когда число х кратно q(а). Но тогда
ах = ат(а). Тем самым показано, что ат(а) — единствнный идемпотент среди степеней элемента а. Теорема доказана полностью.

8. Теорема. Множество {ап(а), ап(а)+1 ,…,ап(а)+q(а)-1} является
циклической подгруппой с единицей ат(а) и порождается элементом ат(а)+1.

Доказательство. Заметим, что так как m(а) есть кратное числа
q(a), то ат(а)+1ат(а)+1=ат(а)+2. В самом деле, для любого
i(am(a)+1)i=am(a)+i, к тому же, если m(a)+i>n(a)+q(a)—1, то
ат(а)+1=ат(а)+i-q(а). Следовательно, множество, порождаемое элементом ат(а)+1совпадает с множеством {an(a), an(a)+1,…,ап(а)+q(а)-1}. В частности, (аm(а)+1)q(а)=аm(а) и (аm(а)+1)q(а)+1=аm(а)+1 и потому в силу элементарных фактов теории групп последнее множество будет циклической группой порядка q(а) с единицей аm(а).

9. Теорема. Произвольная степень ах элемента а принадлежит
подгруппе моноида тогда и только тогда, когда х≥ п(а).

Доказательство. Половина теоремы 9 уже доказана в теореме
8 Поэтому предположим, что х<п(а). Из основ теории групп
известно, что если элемент ах принадлежит конечной группе, то ах порождает циклическую подгруппу этой группы и для некоторого у>1 ах = (ах)у = аху. Но это противоречит условию, что aп(a) есть наименьшая степень элемента а, равная одной из него более высоких степеней. Следовательно, элемент ах не может принадлежать никакой подгруппе моноида.

Значение теоремы 9 заключается в том, что, определив числа п(а) и q(а), мы знаем, какие степени элемента а принадлежат подгруппам
и какие не принадлежат, а также сколько имеется таких элементов.

10. Теорема. Теоретико-множественное объединение всех цик­лических групп, расположенных вокруг идемпотента, является груп­пой и содержит в качестве подгруппы каждую подгруппу моноида, расположенную вокруг этого идемпотента,

Доказательство. Пусть Gu — замыкание относительно операции произведения теоретико-множественного объединения всех цикли­ческих групп, расположенных вокруг идемпотента и. В силу своего определения Gu является подмоноидом и для любого элемента а Gu