Дискретная математика: графы и автоматы. Альпин Ю.А - 77 стр.

§ 6. Синтаксический моноид                                     77


   Задача 1. Доказать, что синтаксический моноид языка L8 (см.
конец §4) изоморфен аддитивному моноиду целых чисел.
   Следующие две задачи связывают свойства синтаксического мо-
ноида со свойствами его графа.
    Задача 2. Мультипликативный моноид называется нильпотент-
ным, если он содержит такой элемент 0, что 0x = x0 = 0 для любого
x, причем существует такое k, что произведение любых k элементов
моноида равно 0. Доказать, что синтаксический моноид нильпотентен
тогда и только тогда, когда все пути в графе моноида, длина кото-
рых не меньше числа его вершин, заканчиваются в одной и той же
вершине.
    Задача 3. Доказать, что синтаксический моноид тогда и только
тогда является группой, когда его граф сильно связен.