6-6. КОНЕЧНЫЕ АВТОМАТЫ С ПАМЯТЬЮ

Рассмотрим устройство с входами и выходами. Входом устройства в момент времени будем называть двоичный набор

в котором компонента характеризует значение переменной поступившее на вход устройства в такте его работы (в момент времени Выходом устройства назовем двоичный набор

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

Перенумеруем все входы, выходы и состояния.

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

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

Определение 6-10. Устройство, работа которого задается с помощью таблиц переходов и выходов, называется конечным автоматом с памятью.

Нетрудно установить эквивалентность определений В-2 и 6-10. И в том и в другом случае речь идет об устройстве, работа которого зависит не только от того, что поступило на его вход в данный момент времени, но и от предыстории этого.

Конечный автомат, задаваемый парой таблиц (таблицей переходов и таблицей выходов), часто называют автоматом Мили.

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

Пример 6-16. Проанализировать работу автомата Мили, заданного с помощью следующих таблиц переходов и выходов:

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

Если за начальное состояние автомата взять состояние 0, то получим следующую выходную последовательность:

При этом смена состояний автомата будет происходить следующим образом:

Если же, например, начальным состоянием автомата было состояние с номером 2, то при той же входной последовательности последовательность смены состояний автомата имеет следующий вид:

Последовательность выходов — соответственно

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

Преобразуем таблицы задания автомата к следующей, привычной для нас форме:

Пример 6-17. Преобразовать таблицы задания автомата из примера 6-16.

Новая форма задания автомата выглядит в виде следующих двух таблиц:

(см. скан)

По этим таблицам можно «аписать аналитическое выражение для функций переходов и выходов. На рис. 6-16 показаны области для функций определяемые вышеприведенными таблицами. Соответствующие МДНФ для этих функций имеют вид:

и

(кликните для просмотра скана)

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

Рис. 6-17. (см. скан)

или в Векторной форме!

Сравнивая между собой (6-24) и (6-26), с одной стороны, и (6-31) и (6-32), с другой стороны, мы видим, что эти соотношения совпадают. Таким образом, верно следующее утверждение.

Теорема 6-3. Любой конечный автомат полностью описывается системой РБФ-1 вида (6-31).

Эта теорема сводит задачу анализа и синтеза конечных автоматов к задаче анализа и синтеза схем, работа которых описывается с помощью РБФ-1.

Пример 6-18. Начертить функциональную схему для конечного автомата примера 6-16.

Используя МНДФ для функций и выхода этого автомата, полученных в примере 6-17, получаем функциональную схему, изображенную на рис. 6-17.

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