Основы синтеза конечных автоматов

Автоматное описание

Рассказать о словесном описании некоторого автомата и частом несоответствии высказываний заказчика с требуемым алгоритмом работы.

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

Рис. 3.1. Представление будущего устройства автоматики в виде черного

ящика с входами х_к и выходами у_і.

Словесное описание

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

Набор значений входных сигналов и набор значений выходных сигналов будем обозначать соответственно X_i, Y_i.

Автоматные таблицы

Автоматной таблицей называется таблица, в которой в левой части перечислены все входные наборы, а в правой – соответствующие им выходные наборы состояния АУ. Если АУ имело k входов и j выходов, то таблица будет содержать 2^к строк. Заполнить таблицу можно лишь в том случае, когда входной набор Х_к однозначно определяет некоторый выходной набор Y_i.

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

Пример составления автоматной таблицы без памяти

Словесное описание

трансформатора 110кВ: АУ должен выдать сигнал на отключение выключателя при токе КЗ > 1кА с выдержкой времени 1,5с. При токе < (0,5 - 1)кА через 1,5с необходимо выдать команду на звуковой сигнал, а если при этом температура охлаждающего масла в трансформаторе больше 80^оС, то выдать сигнал на отключение выключателя.

Исходя из условий ТЗ АУ имеет 4 входа и 2 выхода:

Таблица 3.1 – Автоматная таблица без памяти

Необходимо дополнительно уточнить ТЗ у заказчика.

Автомат с памятью

Если не удается составить таблицу так, чтобы каждому входному набору в ней соответствовал единственный выходной набор то данное АУ обладает памятью.

Пример

Вернемся к таблице 3.1.

Если заказчик даст двойной ответ по пункту 11, 13 то нужно вводить элемент памяти.

П.11 – если ранее был звуковой сигнал, то его оставить, если не было, то и не нужно включать.

П.13 – если ранее был звуковой сигнал, то его оставить, если не было, то включить.

Формально память в АУ может быть введена за счет рассмотрения множества внутренних состояний в которых может находиться АУ. Это множество обозначим как Z=z₀,z₁,…,z_n. среди этих состояний выделим начальное – z₀.

Для таблицы 3.1 z₀ – когда звуковой сигнал не включен;

z₁ – когда звуковой сигнал включен;

обозначим эти состояния кружком (рис.3.2.), а дугами укажем возможные переходы из одного состояния в другое.

Рис.3.2. Граф переходов рассматриваемого в примере АУ с памятью,

цифрами 0,1,2,…, 15 обозначены номера наборов входных переменных автомата согласно табл.3.1.

Вместо построения графа необходимую информацию о смене состояния можно свести в специальную таблицу называемую таблицей переходов или таблицей смены состояний. Для рассматриваемого примера эта таблица имеет вид.

Таблица 3.2 – Таблица переходов

Таблица переходов еще не содержит полной информации о работе системы управления: необходимо указать, как формируются выходные наборы подаваемые АУ на объект. Для этого составляется другая таблица, называемая таблицей выходов. В отличие от таблицы переходов, где на пересечении строк и столбцов стоят указания на внутренние состояния, в которое переходит АУ при данной комбинации внутреннего состояния и входного набора, в таблице выходов для этой комбинации указывается формируемый АУ выходной набор.

Таблица 3.3 – Таблица выходов

Совокупность таблицы переходов и таблицы выходов определяет функционирование автомата с памятью. Объем памяти АУ определяется числом внутренних состояний, использованных в этих таблицах. Таблицы переходов и выходов называют автоматными таблицами.

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

Автоматические устройства у которых выходной набор однозначно определяется тем внутренним состоянием, в котором они находятся после окончания перехода называются автоматами Мура.

У автомата Мура таблица выходов имеет вид:

Таблица 3.4 – Таблица выходов

АУ у которых выходной набор определяется не только состоянием, в котором автомат находился в момент подачи входного сигнала, но и входным набором, поданным на автомат, называются автоматами Мили.

Любое автоматное описание эквивалентно преобразуется либо в автомат Мура, либо в автомат Мили.