Классификация управляющих автоматов

Среди управляющих автоматов выделяют три основные группы:

1) конечные и бесконечные автоматы. Бесконечными являются автоматы, в которых некоторые из алфавитов , , – бесконечны. Это наиболее общий класс автоматов. Большая общность таких автоматов снижает их практическое значение. Из-за этого данная группа автоматов не нашла широкого применения. Наиболее распространенным является класс конечных автоматов, в которых алфавиты , , – конечны;

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

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

Кроме этих основных групп выделяют еще и другие автоматы, которые принадлежат к конечным, но имеют свою специфику:

- нечеткие, их можно получить благодаря обобщению обычного конечного автомата путем изменения функций переходов и выхода нечеткими отношениями;

- без памяти, для которых каждая исходная буква полностью определяется входной буквой, поступившей в тот же момент времени. Эти автоматы называют еще функциональными элементами;

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