Теория автоматов Определение автомата и его разновидности. Таблицы и графы переходов и выходов. Подавтоматы. Теорема о приведенном автомате Операции с автоматами Преобразование автомата Мили в автомат Мура и автомата Мура в автомат Мили

Типы конечных автоматов

1. 
   по закону функционирования ЦА делятся на автоматы 1-го рода (автоматы Мили) и ЦА 2-го рода. Последние автоматы в случае, когда нет явной зависимости от входных сигналов x(t), являются автоматами Мура. Видимо, целесообразнее по первому критерию автоматы делить на автоматы Мили и Мура;
   

(1.12)

(1.13)

Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[] обнаруживается только при наличии символа во входном канале x[].

Рис. 1.3. Функциональная схема автомата Мили.

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

(1.14)

Особенностью автомата Мура является то, что символ y[] в выходном канале существует все время пока автомат находится в состоянии q[].

Рис. 1.4. Функциональная схема автомата Мура.

2. 
   по конечности множеств X, Y, и S автоматы бывают конечными и бесконечными. Может быть, данный критерий стоит трактовать как критерий по мощности ЦА;
   
3. 
   по объему памяти автоматы делятся на автоматы с памятью (последовательностные автоматы) и автоматы без памяти (логические комбинационные схемы);
   
4. 
   по степени раскрытия структуры автоматы бывают абстрактными автоматами (детали структуры не раскрыты) и структурными автоматами (раскрыты детали структуры);
   
5. 
   по отношению между автоматами среди автоматов можно выделить подавтоматы, надавтоматы. Если, например, известно, что ЦАА < ЦАВ, то автомат А является подавтоматом автомата В, а автомат В - надавтоматом автомата А;
   
6. 
   по полноте используемых переходов автоматы делятся на полностью определенные автоматы и частично определенные автоматы;
   
7. 
   по стабильности периода следования входных сигналов автоматы бывают синхронными автоматами (период следования входных сигналов- постоянная величина) и асинхронными автоматами (период - переменная величина);
   
8. 
   по вероятности переходов автоматы делятся на детерминированные (не вероятностные) и недетерминированные (вероятностные) автоматы;
   
9. 
   при нулевой мощности множества внутренних состояний (| S |= 0) автомат называется автономным, при | Y | = 0 - автоматом без выхода. Если среди состояний автомата выделяется начальное состояние s0, то автомат называется инициальным;
   
10. 
    по применению автоматы можно разделить на автоматы:
    

б) сельскохозяйственные (доильные, раздаточные, уборочные и др.);

в) торговые (газетные, упаковывающие, взвешивающие и др.);

г) учебные (обучающие, тестирующие, моделирующие, демонстрирующие и др.);

д) медицинские (искусственные органы, хирургические, диагностирующие, дыхательные, тренирующие и др.);

е) информационные (видеомагнитофоны, системы "вопрос - ответ" и др.).

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

(1.16)

Рис.1. 5. Функциональная схема С-автомата.

Интересно выделить особые классы автоматов, математические модели которых опираются только на два носителя алгебры.

Пусть X=. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.17)

(1.18)

Функциональная схема автомата приведена на рис.1.6.

Рис.1.6. Функциональная схема порождающего автомата.

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

Пусть Y=. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.19)

q[1] = (q[];x[]); (1.20)

Функциональная схема автомата приведена на рис.1.7.

Рис. 1.7. Функциональная схема распознающего автомата.

Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (q_i[];x_i[]) и перевод автомата в заключительное состояние q_k. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

Пусть Q=. Тогда математическая модель и система рекуррентных соотношений имеют вид:

(1.21)

y[] = (x[]); (1.22)

Функциональная схема автомата приведена на рис.8.

Рис. 1.8. Функциональная схема комбинационного автомата.

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

"1" в алгебре автоматов. С - автомат

Любая алгебра должна иметь конструкции, выполняющие в ней роль "0" и "1". По аналогии с алгеброй алгоритмов роль "0" выполняет пустой автомат (ноль-автомат), ЦА0. Пустой автомат – это автомат, в котором запрещены всевозможные переходы. Естественно, что ЦАА \/ ЦА0 = ЦАА, ЦАА /\ ЦА0 = ЦА0.

Роль "1" возлагается на полный ЦА (ЦА1), в простейшем случае такой автомат представляет собой настраиваемое объединение рассматриваемых автоматов. Естественно, что ЦАА \/ ЦА1 = ЦА1, ЦАА /\ ЦА1 = ЦАА, дополнение ЦА1 = ЦА0, дополнение ЦА0 = ЦА1.

Равенство, равносильность, эквивалентность, изоморфизм

Автоматы равны тогда, когда у них одинаковое описание.

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

Два автомата считаются изоморфными, если выполняются следующие два условия:

1. 
   между X, Y и S обоих автоматов можно установить взаимно однозначные соответствия;
   
2. 
   при учете этих соответствий автоматы оказываются равными.