Группы и полугруппы, определенные автоматом Мили

ДИПЛОМНАЯ РАБОТА

Группы и полугруппы, определенные автоматом Мили

Вступление

1. Предварительные сведения

2. Два специальных класса автоматов

3. Автомат без ветвлений

3.1 Группы, определенные обратимым автоматом без ветвлений

3.2 Полугруппы, определенные автоматом без ветвлений

4. Медленный автомат

4.1 Автомат конечного типа

4.2 Преобразования, определенные обратимым медленным автоматом конечного типа

5 Необратимый медленный автомат конечного типа

6. Автомат Мили конечного роста

7. Функции перехода без предельного цикла Заключение Список литературы

Вступление

Одной из основных моделей устройств управления процессами является автоматная модель. Она является универсальной и охватывает все устройства управления, начиная с простейших логических схем (вырожденный автомат с одним состоянием) и заканчивая микропроцессорным управлением и управлением с помощью универсальной ЭВМ.

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

Одной из основных операций над автоматами является суперпозиция (композиция, последовательное соединение) автоматов, т. е. выход одного из автоматов подается на вход другого. Этой операции соответствует композиция автоматных преобразований. Все автоматные преобразования образуют полугруппу относительно операции композиции (полугруппой называется множество с определенной на нем бинарной ассоциативной операцией). Множество всех обратимых автоматных преобразований образует группу. Множество автоматных преобразований, определяемых автоматом во всех его состояниях, порождает полугруппу, которая называется полугруппой порожденной (неинициальным) автоматом. Эта полугруппа состоит из всех преобразований, которые реализуются некоторой степенью автомата (т.е. последовательным соединением автомата с такими же автоматами, но находящимися в других состояниях). Исследование полугруппы, порожденной автоматами — это фактически исследование свойств автоматов относительно операции композиции. Так как эта операция является одной из основных для автоматов, то эти исследования достаточно важны для теории и практики.

Автоматы Мили оказались удобным средством задания групп и полугрупп. Дело в том, что небольшие (по количеству внутренних состояний и символов алфавита) автоматы Мили порождают сложно устроенные полугруппы или группы. Группы, определяемые автоматами, были рассмотрены еще в начальном периоде развития теории автоматов. Группы, порождаемые некоторыми классами автоматов, были рассмотрены Григорчуком, Некрашевичем и Сущанским в. В работах И. И. Резникова полностью исследованы полугруппы и функции роста автоматов с двумя состояниями над алфавитом из двух букв.

Данная работа является продолжением исследований, начатых в [4], где рассматриваются два специальных класса автоматов: автомат без ветвлений и медленный автомат над двоичным алфавитом. Этот частный случай очень часто встречается на практике и соответствует последовательным двоичным устройствам.

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

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

Также покажем, что в работе А. С. Антоненко были получены необходимые и достаточные условия на функции переходов, при которых все автоматы Мили порождают конечные полугруппы.

1. Предварительные сведения

автомат мили ветвление цикл

Определение 1. Конечным автоматом (Мили) называется объект, состоящий из трех конечных непустых множеств и двух функций и , определенных на этих множествах. Множество называется множеством состояний автомата, множество — входной алфавит, а множество — выходной алфавит. Функция носит название функции переходов автомата. Она осуществляет однозначное отображение множества в множество. Функция осуществляет однозначное отображение множества в множество и называется функцией выходов автомата.

Мы будем рассматривать только конечные автоматы, у которых входной и выходной алфавиты совпадают. Обозначим такой автомат четверкой .

Пусть — полугруппа всех преобразований множества (полная полугруппа преобразований),

— группа всех взаимно однозначных преобразований множества (полная симметричная группа), — множество конечных слов над и — множество бесконечных слов (-слов) над .

Удобно описывать конечные автоматы с помощью диаграмм Мура. Мы будем использовать их следующую модификацию. Диаграмма Мура автомата — это ориентированный мультиграф с помеченными ребрами и вершинами, с множеством вершин. Вершины и на графе соединены ориентированным ребром от к и помечены, если. Здесь, Каждая вершина отмечена преобразованием алфавита, которое соответствует выходной функции в состоянии. Т. е. где .

Функции могут быть естественно расширены до отображений множества во множества и с помощью следующих равенств:

где — пустое слово, , и. Функция также может быть расширена естественным образом до отображения .

Определение 2. Преобразование, определенное равенством, где, называется автоматным преобразованием, определенным автоматом в состоянии .

Автомат мили, где , определяет множество автоматных преобразований над .

Определение 3. Автомат Мили называется обратимым, если все его преобразования из множества взаимно однозначны.

Легко показать, что обратим тогда и только тогда, когда преобразование является перестановкой множества для каждого состояния .

Определение 4. Автоматы Мили, , называются изоморфными, если существуют 2 перестановки и взаимно однозначное отображение такое, что

для всех .

Определение 5. Автоматы Мили, , называются эквивалентными, если

.

Утверждение 6. Каждый класс эквивалентности автоматов Мили над алфавитом содержит, с точностью до изоморфизма, единственный автомат, минимальный по отношению к числу состояний (такой автомат называется приведенным).

Минимальный автомат может быть найден с помощью стандартных алгоритмов минимизации.

Определение 7. Для, пусть — произвольный автомат Мили. Автомат, у которого функции перехода и выхода определяются как где , называется произведением автоматови .

Утверждение 8. Для любых состояний и произвольного слова выполняется следующее:

Определение 9. Полугруппа, порожденная множеством преобразований, определенных автоматом Мили во всех его состояниях, называется полугруппой, порожденной автоматом. В случае обратимого автомата группа, порожденная множеством, называется группой, порожденной автоматом .

2. Два специальных класса автоматов

В этой главе мы рассмотрим два специальных класса автоматов. Будем использовать следующую классификацию состояний автомата.

Определение 10. Пусть .-.конечный автомат. Будем называть состояние

· Состоянием покоя, если для любого (автомат останется в этом состоянии)

· Состоянием безусловного перехода, если существует , такое что и для любого .

· Состоянием ожидания, если существует такой что, и для любого ,. Также будем называть такое состояние ждущим .

· Состоянием условного перехода или ветвления, если существует два отличных символа таких, что .

· Состоянием мульти-ожидания, если существует и такое, что и для каждого и для каждого

· Циклическим состоянием, если существует непустое слово такое, что .

Определение 11. Будем называть автомат автоматом без ветвлений, если все его состояния — либо состояния покоя, либо безусловного перехода.

Другими словами, функции перехода автомата без ветвлений зависят только от текущего состояния и не зависят от входного символа. Поэтому для любого, будем обозначать через

Определение 12. Будем называть автомат медленным, если все его состояния либо состояния ожидания, либо состояния покоя.

Другими словами, для любого состояния, существует не более одного символа, такого, что .

Определение 13. Преобразование называется медленным (без ветвлений), если оно может быть определено медленным автоматом (автоматом без ветвлений).

Пример 14. Рассмотрим пример медленного автомата над двухсимвольным алфавитом, показанном на рисунке 1. Будем рассматривать конечное слово как двоичное число. Через обозначим медленное преобразование, определенное автоматом в состоянии. Тогда прибавляет единицу к каждому входящему двоичному числу. Поэтому этот автомат называется «складывающей машиной».

Рассмотрим преобразование. Ясно, что добавляет двойку к каждому входящему двоичному числу.

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

Таким образом, произведение двух медленных автоматов (преобразований) не медленный автомат (преобразование) в общем случае.

Рисунок 1. Складывающая машина.

3. Автомат без ветвлений

Определение 15. Преобразование слова называется посимвольным, если

где

Лемма 16. Преобразование, определенное автоматом без ветвлений, будет посимвольным.

Преобразование f полностью определяется словом. Обозначим соответствующее преобразование через :

Обозначим через циклическую подгруппу группы подстановок :

где ,

здесь и далее сложение по модулю

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

И будем говорить, что.

Лемма 17. Пусть — преобразование, определенное автоматом без ветвлений с состояниями. Тогда, где и — периодическое слово. Причем, длина периода не превышает .

Доказательство. Пусть — автомат без ветвлений, тогда — преобразование, соответствующее состоянию, где .

Обозначим .

Рассмотрим последовательность, где. Члены этой последовательности принадлежат множеству, которое состоит из элементов.

Следовательно, среди первых элементов есть два эквивалентных

, где.

Пусть. Фиксируем . Применяя, мы получим, что Следовательно,

Поэтому последовательность периодическая, начиная с. Из этого следует, что последовательность периодическая, начиная с. Длина периода не превосходит .

3.1 Группы, определенные обратимым автоматом без ветвлений

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

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

Будем говорить, что матрица над кольцом имеет ранг равный нулю, если все элементы матрицы равны нулю. В остальных случаях рангом матрицы над кольцом является наименьшее такое, что матрица может быть представлена как

над кольцом, где -, а — матрицы.

Применима следующая теорема.

Теорема 18. Пусть — обратимый автомат без ветвлений над алфавитом, (разложимо на произведение различных простых множителей) такой, что определенное им преобразование и — количество его состояний. Тогда определенная им группа изоморфна группе, где .

Сначала докажем вспомогательные леммы. Пусть, где, .

Мы можем сопоставить каждое слово, имеющее длину с отображением

Лемма 19. Композиция инвертируемых отображений и — это отображение, где, сложение по модулю как в группе .

Доказательство очевидно.

Лемма 20. Пусть — обратимый автомат без ветвлений над алфавитом, такой, что определенное им преобразование и n — количество его состояний, а — наименьшее общее кратное длин периодов последовательностей. Тогда определенная им группа вкладывается в группу, где, а если разложимо на произведение различных простых множителей, то изоморфна группе .

Доказательство.

Обозначим через группу, определенную автоматом. Отметим, что все преобразования коммутируют между собой. Так, каждый элемент из — это композиция определенных преобразований. Преобразование, где — этоая строчка матрицы (- период любой последовательности начиная сго члена). Композиция этих преобразований — это преобразование, где — это сумма соответствующих строк.

Если любое, то каждый элемент из — это отображение, где — линейная комбинация строк матрицы в линейном пространстве над кольцом. Пусть, то есть представима в виде где -, а — матрицы.

Т.е.

Вектор единственным образом может быть представлен линейной комбинацией векторов, где .

Установим соответствие между элементами, ивекторами коэффициентов линейной комбинации линейно независимых векторов, представляющих вектор. Операция композиция соответствует операции сложения векторов коэффициентов из, где .

Таким образом, .

Если простое, то каждый элемент из — это отображение, где есть линейная комбинация строк матрицы в линейном пространстве над полем. В матрице линейно независимых строк. Вектор единственным образом может быть представлен линейной комбинацией линейно независимых строк матрицы .

Установим взаимно однозначное соответствие между элементами, ивекторами коэффициентов линейной комбинации линейно независимых строк матрицы, представляющих вектор. Операция композиция соответствует операции сложения векторов коэффициентов из .

Таким образом, в случае, когда — простое число, группа изоморфна .

Если, где, , — различные простые числа, то. Каждому элементу матрицы ставим в соответствие элемент, тогда матрица. Затем рассматриваем каждую матрицу, отдельно над полем и получаем, что изоморфна, где — ранги матриц соответственно, а .

Доказательство теоремы 18.

Надо показать, что, для этого, пусть — минимальный номер, такой что первые столбцов матрицы линейно независимы, а первые линейно зависимы.

Тогдаый столбец — это линейная комбинация предыдущих столбцов:

где — этоый столбец матрицы,. Мы можем записать (1) более подробно:

Докажем, что

для всех от 0 до

Действительно, зафиксируем произвольное между 1 и. Положим. Тогда Таким образом, (2) доказано. Из (2) мы можем сделать вывод, по индукции, что столбец для любых — это есть линейная комбинация столбцов. Так как, мы можем заключить, что.

Теорема 18 позволяет описать группы, определенные обратимым автоматом без ветвлений с тремя состояниями.

Определение 21. Две функции перехода называются эквивалентными, если существует перестановка такая что Для автомата без ветвлений равенство принимает вид

Рисунок 2: Схемы функций перехода обратимого автомата без ветвлений с тремя состояниями.

Существует 7 классов эквивалентности функций перехода обратимого автомата без ветвлений с тремя состояниями. Они могут быть описаны с помощью схем (Рисунок 2).Крест обозначает состояние покоя; точка — состояние безусловного перехода. Стрелки обозначают действие функций перехода. Рассмотрим для примера автомат с функцией перехода, соответствующей схеме 7.

Схема 7. Пусть.

Если тогда ранг равен 1.

Если тогда ранг равен 2.

Если тогда ранг равен 3.

Если тогда ранг равен 2.

Если тогда ранг равен 2.

Если тогда ранг равен 2.

Если тогда ранг равен 1.

3.2 Полугруппы, определенные автоматом без ветвлений

Пусть, где, .

Мы можем сопоставить каждое слово, имеющее длину с отображением

Лемма 22. Композиция инвертируемых отображений и — это отображение, где, за обозначена покомпонентная композиция векторов.

Доказательство очевидно.

Теорема 23. Пусть — автомат без ветвлений, и пусть — количество его состояний, а — наименьшее общее кратное длин периодов последовательностей

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

где — полугруппа, порожденная.

Доказательство. Полугруппа, определенная автоматом, порождена преобразованиями, которые, согласно Лемме 17, представимы в форме, где периодическое слово, Из определения, представимо в форме, где. Наконец, изоморфизм следует из Леммы 22.

4. Медленный автомат

Класс медленных автоматов очень широк, и довольно сложно исследовать алгебраические свойства преобразований, определенных медленным автоматом в общем случае. Поэтому будем рассматривать еще один класс автомата, называемого автоматом конечного типа, и исследуем преобразования, определенные медленным автоматом этого класса.

4.1 Автомат конечного типа

Определение 24. Конечный автомат называется автоматом конечного типа, если последовательность состояний для любого конечного входного слова и любого начального состояния стабилизируется.

Определение 25. Преобразование конечных слов называется конечным автоматным преобразованием конечного типа, если существует автомат конечного типа, определяющий преобразование в некотором начальном состоянии.

Довольно просто определить, является ли данный автомат автоматом конечного типа, по его диаграмме Мура.

Утверждение 26. Конечный автомат является автоматом конечного типа тогда и только тогда, когда его диаграмма Мура является ориентированным графом без ориентированных циклов помимо петель.

Доказательство. Необходимость.

Предположим, что диаграмма Мура конечного автомата содержит ориентированный цикл:

Пусть автомат начинает работу из состояния. Тогда существует последовательность входных символов такая, что автомат будет последовательно находиться в состояниях

.

Поэтому, последовательность состояний не стабилизируется.

Достаточность. Возьмем начальное состояние и последовательность входных символов. Обозначим соответствующую последовательность состояний автомата через. Если автомат был в некотором состоянии и затем перешел в некоторое другое состояние, тогда он больше не сможет вернуться в состояние (так как диаграмма Мура не содержит ориентированных циклов кроме петель). Следовательно, для каждого состояния существует не больше, чем один номер, такой, что, это означает, что существует только конечное число, для которого, поэтому последовательность стабилизируется.

Отметим, что произведением двух медленных автоматов (преобразований) не обязательно является медленный автомат (преобразование) (пример 14). Но в отличие от медленного автомата, класс автоматов конечного типа замкнут относительно произведения.

Утверждение 27.

1. Произведением двух автоматов конечного типа является автомат конечного типа.

2. Автомат, обратный инвертируемому автомату конечного типа, есть автомат конечного типа.

Доказательство. Первое предположение следует из определения произведения автоматов: если последовательность состояний первого автомата стабилизирована в состоянии наом шаге, а второго автомата в состоянии наом шаге, тогда последовательность состояний произведения стабилизируется в состоянии на шаге с номером .

Предположение 2. Пусть — обратимый автомат конечного типа. Согласно утверждению 26 его диаграмма Мура не содержит ориентированных циклов помимо петель. Тогда диаграмма Мура обратного для автомата также не содержит ориентированных циклов помимо петель, поэтому он тоже будет автоматом конечного типа.

Следствие 28. Множество всех преобразований автомата конечного типа является подполугруппой полугруппы всех преобразований конечного автомата.

Следствие 29. Множество всех преобразований обратимого автомата конечного типа является подгруппой группы всех преобразований обратимого конечного автомата.

4.2 Преобразования, определенные обратимым медленным автоматом конечного типа

В этом разделе будем рассматривать только обратимые медленные автоматы конечного типа над конечным алфавитом .

Мы рассмотрим алгебраические свойства преобразований такого автомата и определим семейство медленных преобразований конечного типа такое, что каждый элемент является композицией других элементов семейства.

Для описания преобразований, определенных таким автоматом, нам понадобятся операторы, действующие на множестве всех преобразований бесконечных слов. Пусть — некоторая подстановка из множества. Для удобства обозначения расширим действие подстановки на множества посимвольно:

Пусть. Обозначим через отображение, которое действует на входные символы как подстановка до первого появления нуля (включая его), а затем как преобразование. Будем рассматривать как оператор:

Здесь и далее — символ не равный, — конечное слово, состоящее только из неравных символов, .

Определение 30. Пусть. Тогда — это преобразование, которое действует по правилу Операторы Действуют аналогично.

Определение 31. Пусть. Тогда — это преобразование, которое действует по правилу Обозначим множество таких операторов через .

Пример 32. Медленное преобразование преобразовывает слова из следующим образом. Все символы до первого нуля (включительно) инвертируются, затем до первой единицы (после первого нуля), включительно, все символы остаются без изменения, и остальные символы вновь инвертируются.

Такое преобразование определено автоматом, показанным на Рисунке 3.

Любое преобразование, определенное обратимым медленным автоматом конечного типа, может быть представлено с помощью выше описанных операторов.

Утверждение 33. Пусть — медленный обратимый автомат конечного типа. Тогда любое определенное им преобразование может быть представлено в форме Обратное тоже верно: если преобразование может быть представлено в форме (3), то оно может быть определено медленным автоматом конечного типа.

Доказательство. Пусть — обратимый медленный автомат конечного типа. Удалим из его диаграммы Мура все петли. Тогда от каждой вершины будет отходить не более одного ребра (так как все состояния либо состояния ожидания, либо покоя).

К тому же, полученный граф не будет содержать ориентированных циклов (так как — автомат конечного типа).

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

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

Для формулировки свойств представленных операторов нам понадобится еще одно их обозначение. Пусть. Определим

.

Договоримся, что.

Пример 34. Медленное преобразование может быть также представлено в форме Из представления (4) ясно, как именно действует преобразование, и какой автомат его определяет. Однако, представление в форме (5) оказывается более удобным во многих случаях, например, когда требуется найти композицию двух преобразований или обратное преобразование.

Утверждение 35. Операторы из множества обладают следующими свойствами:

1. Взаимно однозначное преобразование под действием оператора в форме превращается во взаимно однозначное, а конечное преобразование автомата в конечное.

.

.

.

взаимно однозначная.

, ,

здесь и далее сложение по модулю.

Доказательство.

Свойство 2 следует прямо из определения оператора .

Докажем свойство 3. Пусть, то есть, и, то есть Рассмотрим действие преобразования на слово в двух случаях

1) и 2) ,

Здесь и далее

Отметим что, поэтому (поскольку взаимно однозначное). Тогда

Свойства 4 и 5 следуют прямо из свойства 3.

Для доказательства свойства 6 будем использовать соотношения (6), которые следуют из свойства 1:

Из (6), применяя свойство 3, мы получим требуемое соотношение.

Первое утверждение свойства 1 следует из уже доказанного свойства 5.

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

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

Из второго свойства утверждения 35 следует, что представление (3) для медленного преобразования конечного типа неоднозначно определено, но всегда может быть приведено к форме:

Будем называть представление (7) каноническим.

Утверждение 36. Любой медленный автомат конечного типа имеет именно одно каноническое представление.

Доказательство. Предположим, что преобразование имеет два различных канонических представления:

Предположим, существует номер такой что, и или.

Либо есть (не теряя общности, можем положить) и .

Этот случай будет рассмотрен позже.

Отметим, что ситуация и невозможна, потому что одно из представлений не будет каноническим.

Если, легко заметить, что где. Это невозможно, так как. Если, тогда найдем максимальный номер такой, что (если, тогда).

Аналогично, — максимальный номер такой, что. Предположим, что, случай может быть рассмотрен аналогично. Тогда несложно заметить, что Где, если и, если (). С другой стороны, Что невозможно, так как.

Осталось рассмотреть случай, когда и .

Есть два варианта:

1.

2.

В первом варианте пусть будет минимальным номером таким, что. В слове символ с номером будет с одной стороны и с другой. Во втором варианте в слове символ с номером будет с одной стороны и с другой. Следовательно, в любом случае мы получаем противоречие.

Далее будем рассматривать только двухсимвольный алфавит .

Рассмотрим семейство медленных преобразований конечного типа:

Все являются инволютивными, то есть Мы покажем, что все медленные преобразования конечного типа могут быть представлены композицией .

Теорема 37. Справедливо следующее равенство.

Доказательство. Доказывать будем индукцией по .

Базис индукции:.

Применяя Свойство 6 Утверждения 35, мы получим Если, тогда, а иначе .

Индуктивный переход: Предположим, что утверждение теоремы верно для. Докажем его для :

Применяя Свойство 6 Утверждения 35, мы получим Применяя предположение индукции:

Применяя Свойство 4 Утверждения 35 и соотношение, мы получим

.

Поэтому, медленное преобразование конечного типа может быть представлено как:

где

(10.1) для всех и

(10.2) существует, такое что, если, и, если .

На самом деле, если — последовательность неотрицательных чисел, удовлетворяющих условиям (10.1) и (10.2), тогда из Теоремы 37 следует, что преобразование является медленным преобразованием конечного типа (не сложно выбрать соответствующие).

4.3 Необратимый медленный автомат конечного типа

Рассмотрим медленный автомат конечного типа над двухсимвольным алфавитом, являющийся обобщением соответствующего обратимого автомата, изученного в Разделе 5.2. Для описания преобразований, определенных таким автоматом, нам потребуется расширить множество операторов, рассмотренных в Разделе 5.2.

Пустьнекоторое преобразование из множества =. расширим действие преобразования на множества и посимвольно, как в Разделе 5.2.

Операторы и определяются также как в Разделе 5.2:

где действует согласно следующему правилу И

где действует согласно следующему правилу Множество. Очевидно что

Утверждение 38. Пусть — медленный обратимый автомат конечного типа. Тогда любое определенное им преобразование может быть представлено в форме Обратное тоже верно: если преобразование может быть представлено в форме (3), то оно может быть определено медленным автоматом конечного типа.

Доказательство аналогично доказательству Утверждения 33.

Введем еще одно обозначение для операторов из :

Запись в форме соответствует записи Раздела 5.2. Установим и Пусть

Утверждение 39. Операторы из множества обладают следующими свойствами:

1. Конечное автоматное преобразование под действием оператора в форме или превращается в конечное.

2.

3.Для всех

4. Для всех

.

5.

6.

здесь и далее сложение по модулю 2.

Доказательство.

1. Доказательство аналогично доказательству Свойства 1 для операторов из .

2. Оно следует из определения .

3. Пусть Тогда, таким образом свойство следует из определения.

4. Пусть Тогда, таким образом свойство следует из определения.

5. Рассмотрим действие левой и правой частей равенства на слова, где и

Используя свойства 3 и 4, мы получим:

6. По свойству 2,

7.

. У нас есть если, тогда Свойство 6 превращается в последнее выражение.

По-другому, если, тогда Свойство 5 даст Если тогда

.

По определению операторов и мы получаем

что доказывает Свойство 6.

Также как в Разделе 5.2 мы введем понятие канонического представления произвольного (не обязательно инвертируемого) медленного автоматного преобразования конечного типа, которое будет единственным.

Пусть

Очевидно, что

Все — инволюции,, всеидемпотенты, т. е. Ясно, что.

Докажем идемпотентность. У нас есть Тогда, Очевидно, что не идемпотент.

Теорема 37 может быть обобщена: все медленные преобразования конечного типа могут быть представлены в форме композиций (или что-то же самое).

Теорема 40. Любое медленное преобразование конечного типа, может быть представлено в форме

Более точно, если, тогда

Где Форма (13) превращается в форму (12) отбрасыванием из композиции (13), кроме случая.

Доказательство. Будем доказывать теорему индукцией по .

Базис индукции. Пусть. Тогда, и

То есть может быть представлена в формах (12) и (13).

Предположим, утверждение теоремы справедливо для, и докажем, что для оно тоже выполняется. Пусть. Тогда и по предположению индукции может быть представлено как. Отметим, что, поэтому Возможны два случая:

Пусть. Тогда откуда следует (13).

Пусть. Тогда

откуда следует (13).

Форма (13) не обязательно минимальна. Чтобы уменьшить число элементов в ней, мы можем убрать фрагменты в форме, которые эквивалентны .

5. Автомат Мили конечного роста

Степень определена для любого автомата и любого положительного числа. Обозначим через минимальный автомат Мили, эквивалентный. Из определения произведения автоматов следует, что .

Определение 41. Функция натурального аргумента, определенная как, называется функцией роста автомата Мили .

Определение 42. Автомат называется автоматом конечного роста (порядка), если его функция роста ограничена.

Легко показать, что автомат будет автоматом конечного роста тогда и только тогда, когда определенная им полугруппа будет конечна.

Определение 43. Сплетение бесконечной последовательности, (конечной последовательности) полугрупп преобразований — это полугруппа всех преобразований множества, удовлетворяющая следующим условиям:

1. если, тогда зависит только от первых координат для ;

2. если фиксирована, то преобразование, порожденное, это преобразование из полугруппы .

Обозначим определенное сплетение полугрупп преобразований через (в случае конечной последовательности).

Пусть — непустое конечное множество состояний. Будем говорить, что функция перехода порождает бесконечную полугруппу (группу) конечных автоматных преобразований, если существует функция выхода такая, что автомат порождает бесконечную полугруппу (группу) автоматных преобразований. Иначе мы говорим, что функция перехода порождает только конечные полугруппы (группы) конечных автоматных преобразований.

Функция перехода без ветвлений порождает только конечную полугруппу или группу. Однако существуют другие функции перехода и, поэтому, другие классы автоматов, которые порождают только конечные полугруппы. Наиболее общий (но не максимальный) класс задан Резниковым в следующей теореме.

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

Пусть будем писать. Определим. Докажем по индукции, что

Для мы имеем, где — пустое слово. Предполагая, что для, для имеем

Пусть — непустое множество такое, что (в частности, можно установить, что когда). Пусть. Если, тогда существуют слово и состояние такое, что и, соответственно,, Следовательно, , откуда. Поэтому, если, тогда равенство выполняется для любого числа .

Кроме того, для любого натурального имеем. Пусть.

Если для некоторого, тогда. Так как множество конечно, то всегда существует такой, что. Кроме того. Получаем Складывая все свойства, получаем следующую лемму.

Лемма 45. Пусть — непустое множество состояний такое, что. Множества, , удовлетворяют следующим равенствам:

1.

2. существует такое, что

3. Для любого,

Напомним, что приведенные утверждения справедливы и для случая. В этом случае мы имеем следующую характеристику множества .

Лемма 46. Множество состоит из всех состояний, доступных из некоторого циклического состояния.

Доказательство. Обозначим через множество всех состояний, доступных из некоторого циклического состояния. Пусть — циклическое состояние, т. е. для некоторого непустого слова имеем. Пусть, тогда. Имеем .

Применяя (14), для каждого натурального получаем т. е. Пусть будет доступен из, т. е. для некоторого слова мы получаем. Так как, имеем. Из Леммы 45. Поэтому. Следовательно, все состояния, доступные из циклического принадлежат, т. е.

Докажем, что. Пусть и пусть, тогда по лемме 45, т. е. существует такое, что, когда. Определим, где. Так как число состояний, среди первых состояний есть два одинаковых. Пусть. Так как — циклическое состояние. Более того, доступно из циклического состояния, т. е. Мы получаем,, поэтому, что доказывает лемму.

Подобно доказательству Леммы 46, если, тогда множество состоит из состояний, которые доступны из циклических состояний, принадлежащих .

Определение 47. Пусть — конечное множество состояний. Функция перехода называется функцией перехода с предельным циклом, если множество состоит из состояний без ветвлений, иначе она называется функцией перехода без предельного цикла.

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

Доказательство. Пусть обозначает полугруппу, порожденную автоматом. Пусть содержит только состояния без ветвлений, и пусть (так как номер всегда существует по Лемме 45.) Обозначим через автомат с множеством состояний, тем же алфавитом и соответствующим расширениями функции переходов и функции выходов. Этот автомат корректный, потому что из определения. Отметим, что автомат — автомат без ветвлений. Поэтому он определяет конечную полугруппу автоматных преобразований .

Автоматное преобразование, определенное автоматом в состоянии, записывается в форме, где. Так каждое записывается в форме, где. Преобразование однозначно определено функцией и функцией, где. Так как число функций и конечно, то число элементов в конечно.

Эта теорема дает достаточное условие для функций перехода, которые определяют только конечные полугруппы. Далее мы покажем, что это условие является необходимым.

6. Функции перехода без предельного цикла

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

1. Функция перехода определяет бесконечную полугруппу;

2. Для есть циклическое состояние ветвления;

3. функция перехода — функция перехода без предельного цикла (другими словами, содержит состояние ветвления).

Чтобы доказать эту теорему мы проанализируем функции перехода без предельного цикла. Мы рассмотрим три типа таких функций перехода. Для произвольной функции перехода каждого типа построим функцию выхода такую, что автомат определяет бесконечную полугруппу автоматных преобразований. И, наконец, мы выделим некоторые преобразования алфавита для каждого состояния. Зафиксируем несколько элементов множества Обозначим через автоматное преобразование, определенное автоматом в состоянии. Чтобы доказать, что полугруппа бесконечная, мы покажем, что у некоторых элементов бесконечный порядок, а именно мы выберем слово такое, что слова попарно различны. Это условие доказывает, что преобразования над попарно различны, а значит полугруппа бесконечна.

Пусть — функция перехода такая, что содержит состояние ветвления. Рассмотрим все возможные последовательности состояний формы. Каждая из них в конечном итоге периодическая. Так мы можем выделить из них периодические части (простые циклы, отмеченные 0-м на диаграмме Мура) в форме, где. Возможен только один из следующих случаев.

a) Все эти циклы состоят из состояний без ветвлений.

b) Есть цикл, отмеченный 0-м, такой, что существует состояние и символ такие, что (т.е. есть цикл, который мы можем покинуть).

c) Есть цикл с состоянием ветвления, но нет цикла, описанного в b).

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

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

Доказательство. Рассмотрим следующие множества.

· Множество всех состояний таких, что существует неотрицательный номер такой, что для каждого слова длины большей или равной состояние будет состоянием без ветвлений.

· Множество всех состояний, из которых автомат может перейти в состояние из-под действием одного входного символа.

· - множество всех других состояний.

Рассмотрим пример автомата, который удовлетворяет условиям Леммы 50. Пусть и пусть диаграмма Мура будет как показано на Рисунке 4. У нас.

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

Установим (если, тогда установим). Тогда для каждого слова длины большей или равной мы получим.

Так как длина слова больше или равна, т. е. больше или равна, то состояние — состояние без ветвлений. Поэтому, это следует из определения ,. Так как — произвольное состояние из множества, мы делаем вывод, что .Так как конечно, существует и состоит только из состояний без ветвлений, следовательно, все состояния в множестве — состояния без ветвлений. Из условия леммы,, следовательно множества и не пусты, но множество может быть пустое.

Назначим преобразование для каждого состояния из и. Для каждого состояния множество не пусто (иначе для), но оно не совпадает с алфавитом. Для каждого мы выберем произвольный элемент, и назначим для состояния преобразование

Зафиксируем произвольное состояние, слово и преобразование .

Множество — объединение всех несвязных циклов, которые состоят из состояний без ветвлений, — множество всех состояний, из которых автомат всегда переходит в состояние из

Рассмотрим действие автоматного преобразования на произвольное бесконечное слово вида

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

Из конструкции функции выхода следует, что автомат меняет символ входного слова тогда и только тогда, когда он переходит из состояния, принадлежащего множеству, в состояние, принадлежащее множеству. Поэтому отличается от только в — ой позиции. Слово также имеет вид (15), поэтому мы можем провести подобные рассуждения и для него, т. е. отличается от только в позиции (). Более того,, так как автомат «фиксирует» символ в позиции, после которого автомат переходит в состояние из. Обрабатывая входное слово, автомат работает таким же образом, пока не достигнет позиции, т. е.. Но так как и символ расположен наой позиции слова, мы видим, что

.

Поэтому автомат переходит в состояние, принадлежащее, и изменяет символ позднее, т. е. .

Применяя последовательно автоматное преобразование к слову (это слово имеет вид (15)), мы получаем слова вида (15). Каждое из этих слов отличается от предыдущего слова только одним символом (нуль заменяется на ненулевой символ). Более того, позиция этого символа расположена все дальше и дальше от начала слова. Это доказывает бесконечный порядок так же как и бесконечность полугруппы, определенной автоматом.

Функция выхода, сформированная по правилам, описанным в Лемме 50, для примера показана на Рисунке 4. Автоматные преобразования имеют бесконечный порядок, поэтому полугруппа, определенная автоматом также имеет бесконечный порядок. Действительно, и так далее.

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

Доказательство. Не теряя общности, мы можем предположить, т. е. Назначим преобразование состояниям, и преобразование состоянию. На Рисунке 5 приведен пример для случая (показаны только важные преобразования). Возьмем .

Рассмотрим действие автоматного преобразования, где. Из последней конгруэнции следует, что. Поэтому под действием нулей автомат переходит из состояния в состояние и выдает нулей. Тогда под действием символа 1 автомат переходит из состояния в состояние и выдает символ 0. После этого автомат выдает символ 1. Так для некоторого .

Пусть и рассмотрим, где — неотрицательное число. Получим

так как

так как

.. .

где. Поэтому для некоторого слова .

Имеем. По индукции,, что доказывает бесконечность порядка. Поэтому полугруппа, определенная автоматом, бесконечна.

Лемма 52. Пусть — функция перехода такая, что нет цикла, отмеченного 0-м, состояния и символа таких, что. Предположим, что существует 0-цикл, который содержит состояние ветвления, тогда существует функция выхода такая, что порождает бесконечную полугруппу автоматных преобразований.

Доказательство. Не теряя общности, мы можем предположить, что — состояние ветвления. Поэтому существует такой, что. мы можем положить. Рассмотрим циклическую часть последовательности преобразований под действием символа 1 из состояния. Эта часть имеет вид, где. Случай, когда эта циклическая часть не содержит все состояния, подобен Лемме 51 с перестановкой символов 0 и 1 (т.е. существует цикл, отмеченный 1, с выходом 0, по крайней мере, в одном состоянии). В другом случае, мы рассмотрим множество состояний, алфавит и соответствующее расширение функций перехода. Они определяют групповой автомат с двумя различными подстановками и состояний под действием символов алфавита. Здесь и — это подстановка, потому что является сюръективным преобразованием конечного множества самого в себя. Эти две подстановки циклические длины, поэтому их порядки равны. Более того, — циклическая подстановка такая, что. Имеем, потому что — состояние ветвления.

Назначим преобразование для состояния, преобразование для состояний, и преобразование для других состояний. Таким образом мы определили два автомата и, где и — соответствующие расширения для функций и (эти функции корректно определены, потому что и). На Рисунке 6 показан пример. Полугруппа, определенная есть подполугруппа фактор-полугруппы полугруппы, порожденной автоматом. Докажем бесконечность полугруппы, определенной, откуда можно заключить, что полугруппа, порожденная бесконечна.

Для этого установим. Затем так как порядок равен, т. е. автомат вернется в состояние после чтения символов. Пусть, , где — конечное или бесконечное слово.

Имеем для каждого числа такого, что. Также для каждого числа такого, что. Отметим, что не идентичная подстановка. Более того,, так как иначе, это противоречит предположению, что. Пусть порядок подстановки равен. В этом случае для конечного слова, если и только если число единиц в слове делится на, так как каждый блок формы действует на состояние как подстановка, и каждый блок формы действует на состояние, как идентичная подстановка. Поэтому, где ,

т.е.

Так в слове остаются только первая, -ая, -ая и так далее буквы, а все другие меняются на 0.

Докажем по индукции, что для всех, , где. Для имеем. Предположим, что для равенство, выполняется. Тогда для имеем

.

Под действием преобразования получаем

.

Следовательно, слова попарно различны. Следовательно, порядок бесконечный. Поэтому полугруппа, определенная, бесконечна. Поэтому полугруппа, определенная, также бесконечна.

Доказательство Теоремы 49. Пусть условие 2 выполняется, т. е. существует циклическое состояние ветвления для. По Лемме 46 это состояние принадлежит, поэтому условие 3 выполняется.

Пусть условие 3 выполняется, т. е. содержит состояние ветвления. Докажем, что выполняется условие 2. Предположим обратное, что все циклические состояния являются состояниями без ветвлений. Пусть — произвольное циклическое состояние, т. е. для некоторого непустого слова выполняется условие. Тогда — циклическое состояние, так как

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

Докажем от противного, что условие 3 следует из условия 1. Предположим, что функция перехода определяет бесконечную полугруппу, но состоит только из состояний без ветвлений. По Теореме 48 произвольный автомат с функцией перехода определяет конечную полугруппу. Что противоречит нашему условию.

Осталось доказать, что условие 1 следует из условия 3. Пусть условие 3 выполняется, т. е. содержит состояние ветвления. Выше показано, что функция перехода удовлетворяет Леммам 50, 51, 52. Поэтому, существует функция выхода такая, что определяет бесконечную полугруппу автоматных преобразований. Таким образом, функция перехода порождает бесконечную полугруппу автоматных преобразований, что доказывает теорему.

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

Заключение

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