Составные части абстрактного автомата. Способы задания автоматов. Синхронные и асинхронные автоматы. Минимизация полностью определенного автомата. Структурная теория. Канонический метод структурного синтеза автомата. Кодирование состояний автомата. Гонки в автомате. Противогоночное кодирование состояний автомата, страница 3

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

Когда система имеет решение, то говорят, что система полна.

Классы автоматов:

  i.  автомат с памятью

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

В автомате Мура с полной системой выходов можно отождествлять внутренние состояния с выходными сигналами.

Теорема:

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

структурное кодирование состояний автомата структурные состояния автомата

 - структурный входной сигнал объединения автоматов , называемы структурным входным сигналом элементов памяти

Переход автомата из состояния  в состояние  складывается из соответствующих переходов автоматов , образующих его память. Каждый из переходов автоматов  осуществляется под действием входного сигнала , подаваемого на его вход и определяемого с помощью функции входов  этого автомата. Структурные входные сигналы  образуют входной сигнал  автомата. Из функции  строится объединяющая их векторная функция

Отсюда с учетом ранее записанного уравнения  можно записать .

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

 - выходной сигнал некой комбинационной схемы (например, схемы КС1 на рисунке)

 - каноническое уравнение

 – автомат Мили

 – автомат Мура

 формируется КС2

Кодирование состояний автомата

Сопоставление каждому состоянию автомата определенного набора элементарных состояний, образующих его память. Переход из одного состояния в другое – изменение состояния элементов памяти.

Гонки в автомате

При функционировании автомата могут возникать состязания (разное быстродействие, разная задержка сигналов возбуждения, разное время переключения элементов). Если при переходе автомата из одного состояния в другое должны переключиться несколько элементов памяти, то между ними возникают состязания. Тот элемент памяти, который изменит свое состояние быстрее, может через цепь ОС (КС1) изменить состояния других элементов памяти. Это может привести к переходу автомата в состояние, не предусмотренное его алгоритмом функционирования.