Абстрактная теория автоматов
Абстрактным автоматом называется дискретное устройство, задаваемое тремя непустыми множествами ,
,
называемыми алфавитами входных сигналов, выходных сигналов и состояний, и двумя функциями - функцией переходов
, определяющей состояние автомата
в S+1-м такте в зависимости от состояния автомата
и значения входной буквы
в S-м такте
и функцией выходов , определяющей значение выходной буквы
в зависимости от состояния автомата
и входной буквы
в S -м такте
Обычно на множестве фиксируется одно из состояний
в качестве начального (инициальный автомат).
По способу формирования функции выхода выделяют 3 типа абстрактных автоматов: автомат Мили, автомат Мура, С-автомат.
Эти автоматы описываются системой уравнений:
автомат Мили: автомат Мура:
С-автомат:
Будем рассматривать только автоматы детерминированного типа, у которых каждой паре и
однозначно соответствует пара
и
. Функционирование детерминированных автоматов подчиняется следующим условиям:
- любому входному слову из букв (слову длиной
) соответствует выходное слово той же длины,
- двум входным словам, в которых первые букв совпадают, соответствуют выходные слова с совпадающими
первыми буквами, если перед подачей входных слов, автомат находился в одном и том же состоянии.
![]() |
Функции


В таблице 1 приведены произвольная последовательность входных сигналов и соответствующие ей последовательности состояний и выходных сигналов автомата, заданного таблицей переходов и выходов.
Более наглядным является представление автоматов Мили с помощью графов. Граф автомата состоит из узлов (вершин) соединенных ветвями (ребрами). Узлы графа отождествляются с состояниями автомата, а ветви отмечаются входными сигналами, вызывающими переход автомата по данной ветви, и выходными сигналами, соответствующими такому переходу.
Два автомата, у которых совпадают как входные, так и выходные сигналы, называются эквивалентными. если для любого входного слова выходное слово одного автомата совпадает с выходным словом другого автомата.
Для любого автомата Мили можно построить эквивалентный автомат Мура и наоборот. Для этого:
1) поставим каждой паре автомата Мили состояние
автомата Мура;
2) во множество состояний автомата Мура включим начальное состояние автомата Мили. Если автомат Мили имеет
состояний и
входных сигналов, то эквивалентный автомат Мура будет иметь
состояний.
Из таблицы видно, что состояние
автомата Мили совпадает с состояниями
автомата Мура, т.е.
,
,
Значения функции выходов для эквивалентного автомата Мура определяются соотношением:
при
Для начального состояния значение выходного сигнала выбирается произвольно. Т.о. переходы и выходные сигналы эквивалентного автомата Мура определяются таблицей:
![]() |
Задача перехода от автомата Мура к эквивалентному автомату Мили решается очень просто. Если и
– функции переходов и выходов автомата Мура, то функции переходов
и выходов
эквивалентного автомата Мили определяются соотношениями:
;
Т.о. таблица переходов эквивалентного автомата Мили совпадает с таблицей переходов автомата Мура, а таблица выходов составляется так, что в каждую ее клетку записывается сигнал, которым отмечено состояние в данной клетке.
Частичными автоматами называются автоматы, на входы которых некоторые последовательности сигналов никогда не подаются (запрещенные входные слова)
Основными задачами теории автоматов являются задачи анализа и синтеза автоматов. Под анализом автомата понимают установление закона его функционирования по заданной схеме автомата, под синтезом – построение автомата из более простых автоматов по заданному закону функционирования. При решении этих задач наиболее важными являются абстрактный и структурный этап.
На абстрактном этапе автомат задается таблицами или графом или каким-нибудь другим способом. На структурном этапе автомат понимают как структурную схему, состоящую из набора простейших автоматов и ФПС логических элементов.
Дата добавления: 2016-07-18; просмотров: 2839;