Вступление

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

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

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

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

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

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

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

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