Абстрактный синтез конечных автоматов

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 02:26, 20 мая 2016.

Условия эквивалентности Колдуэлла

Начальный автомат

Для упрощения автомата в первую очередь необходимо выделить эквивалентные состояния.

Состояние 0 1

Условия эквивалентности Колдуэлла:

  1. Необходимое условие: внутренние состояния и называются эквивалентными, если при подаче произвольной входной последовательности с начальными состояниями и образуются одинаковые выходные последовательности.
  2. Достаточное условие: если две одинаковые строки выходят в следующее состояние, то эти состояния эквивалентны.

Условия эквивалентности Колдуэлла состоит из 2 условий:

  • Условие совпадения выходов (необходимое)
  • Условие совпадения следующих состояний (достаточное)

Для нашего примера:

Конечный автомат
Состояние 0 1

Минимизация Конечного Автомата

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

Минимизация конечных автоматов означает решение следующей задачи: как данному детерминированному, полному Конечному Автомату найти эквивалентный ему с наименьшим возможным количеством состояний. Из двух детерминированных автоматов, допускающих один и тот же язык, меньше памяти при реализации занимает тот автомат, у которого меньше состояний.

Число состояний автомата можно уменьшить, удалив те состояния, которые не используются при анализе допустимых цепочек.

Автоматы упрощаются/минимизируются:

  1. Удалив недостижимые состояния;
  2. Удалив непродуктивные состояния;
  3. Выявив эквивалентные состояния.

Для описания процесса нахождения наименьшего Конечного Автомата введем следующие определения:

TemplateDifinitionIcon.svg Определение «Определение - Недостижимое состояние »

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

TemplateExampleIcon.svg Пример Пример

В следующем Конечном Автомате состояние – недостижимое. Рисунок 2.1.

Рисунок 2.1


TemplateDifinitionIcon.svg Определение «Определение - Непродуктивное состояние »

Непродуктивным называется то состояние для которого не существует для которого .


TemplateExampleIcon.svg Пример Пример

В следующем Конечном Автомате состояние – непродуктивное. Рисунок 2.2.

Рисунок 2.2


Известно, что два автомата называются эквивалентными, если они распознают один и тот же язык над алфавитом.


TemplateDifinitionIcon.svg Определение «Определение »

Говорят, что слово различает состояния , если одно из этих состояний финальное, а другое не является заключительным.

TemplateDifinitionIcon.svg Определение «Определение - Неэквивалентные состояния »

Состояния и конечного автомата называются различными (неэквивалентны), если существует слово (цепочка) , которое различает эти два состояния (из одного состояния достижимо заключительное состояние, а из другого — нет).

TemplateDifinitionIcon.svg Определение « Утверждение »

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

Описание алгоритма минимизации конечного автомата

Описание алгоритма минимизации конечного автомата:

  1. Находим и удаляем в начальном Конечном Автомате все недостижимые и непродуктивные состояния.
  2. Затем необходимо найти такое разбиение множества всех оставшихся состояний автомата, чтобы каждое подмножество содержало неразличимые состояния. То есть множества состояний автомата разделяются на классы эквивалентности:
    1. В I-й класс относим все конечные/финальные состояния (то есть состояния из множества);
    2. Во II-й класс относим все остальные состояния (то есть).
  3. Назовем эти состояния -эквивалентными.Строим новое одно-эквивалентное разбиение, выделив те состояния, которые по одинаковым символам переходят в -эквивалентные состояния.
  4. Повторяется шаг 3, последовательно создавая -эквивалентные состояния по -эквивалентным, увеличивая так число классов эквивалентности.
  5. Алгоритм заканчивается, когда-эквивалентные состояния совпадают с -эквивалентными.

Каждый полученный класс эквивалентности будет новым состоянием в новом минимизированном автомате. В множество автомата внесём те состояния, которые содержат хотя бы одно финальное состояние из начального. Полученный, минимизированный Конечный Автомат должен быть эквивалентен начальному Конечному Автомату.

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

Задача кодирования Конечного Автомата и способы её решения (Код Грея)

TemplateDifinitionIcon.svg Определение «Определение - Кодирование состояний автомата »

Кодирование состояний автомата — установление соответствия между состояниями автомата и наборами значений кодирующих их переменных. Кодирование состояний автомата — один из этапов синтеза автоматов структурного.

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


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

TemplateDifinitionIcon.svg Определение «Определение - Соседи I рода. »

Два состояния автомата и называются “соседями I рода”, если под воздействием хотя бы одного и того же входного символа из них осуществляется переход в одно и то же состояние.

TemplateDifinitionIcon.svg Определение «Определение - Соседи II рода »

Два состояния автомата и называются “соседями II рода”, если в эти состояния осуществляется переход под воздействием хотя бы одного и того же входного символов из состояний, которые являются “соседями I рода”.

Суть способа кодирования состоит в том, что состояния, являющиеся соседями I рода и II рода, кодируются соседними кодами. Два двоичных кода одной длины называются соседними, если они различаются значением только в одном разряде.

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

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

TemplateExampleIcon.svg Пример Пример

На рисунках представлены преобразователи двоичного кода в код Грея (рисунок 3.1.) и кода Грея в двоичный код (рисунок 3.2.), реализованные на элементах ИСКЛЮЧАЮЩЕЁ ИЛИ.

Рисунок 3.1.
Рисунок 3.2.


Каноническая форма синхронного Конечного Автомата

Автомат называется синхронным, если его состояния меняются в строго определенные моменты времени, заданные с помощью специальных сигналов синхронизации. После очередного синхронизирующего сигнала с учетом «считанного» происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Таким образом, реакция автомата на каждое значение входного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами Канонические.

TemplateDifinitionIcon.svg Определение «Определение - Синхронные конечные автоматы () »

Синхронные конечные автоматы () это устройства, структура которых может быть представлена в виде конструкции из модулей двух типов - комбинационной схемы (), на рисунках обозначение – (combinational logic), и регистра – (register) с динамической синхронизацией (Рисунок 4.1).

Рисунок 4.1. Структурная схема cинхронного автомата


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

Абстрактный конечный автомат это - математическая структура с тремя основными множествами .

- называется множеством входных символов;
- называется множеством выходных символов;
- называется множеством (символов) состояний.

Абстрактный конечный автомат функционирует в автоматном времени определяемом как упорядоченное множество целых чисел. Это означает, что автоматное время дискретно, и существенным является лишь номер момента времени; упорядоченность множества означает, что автоматное время имеет «направление». Если обозначить через , , переменные со значениями в соответствующих множествах в момент , то работа абстрактного конечного автомата описывается уравнениями, которые называются каноническими:



- называется оператором перехода. Оператор перехода , кроме вычисления значения, выполняет также сдвиг во времени этого значения.
- называется функцией выхода;
Принята также другая форма записи канонических уравнений:



Знак двоеточие означает операцию сдвига значения на единицу времени или иначе – операцию запоминания; – функцию перехода. Для фиксированного момента времени аргумент время в записи уравнений можно опустить, а так же идентифицировать конкретные значения переменных, например с помощью индексов:



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


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



Каждый очередной выходной символ однозначно определяется последовательностью ранее поступивших входных символов, т.е. вычисление имеет свою “историю”. Эта история сохраняется в автомате в виде переменной – состояние. Состояние автомата - это та минимальная информация, которая необходима для предсказания дальнейшего поведения автомата. Поведение автомата трактуется как переходы из одного состояния в другое состояние в определенные моменты автоматного времени с одновременным вычислением выходного значения.

Для того чтобы абстрактный конечный автомат адекватно моделировал , необходимо выполнение некоторых соглашений.

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

Регистр в запоминает код состояния. Состояния кодируются двоичными наборами. Количество разрядов памяти, а значит и кода состояния, называется мерностью автомата. в свою очередь реализуют функции переходов и выхода. Ход времени в инициируется изменением значения единственного сигнала - сигнала синхронизации . На каком-либо из фронтов этого сигнала изменяется содержимое , а значит и состояние автомата (в схемах на рисунок 4.1. переключается по положительному (нарастающему) фронту сигнала ). Переключающие фронты сигнала будем называть рабочими фронтами. Интервал времени между соседними рабочими фронтами называется тактовым интервалом или просто тактом . Для абстрактного автомата не имеет смысла понятие такта, как некоторого интервала «непрерывного» времени. (Применительно к абстрактному автомату можно понимать термин такт как изменение дискретного времени на одну единицу). Для реального синхронного цифрового автомата величина этого интервала один из важнейших технических параметров, определяющих быстродействие схемы. Величина этого интервала должна быть достаточной для того, чтобы закончились переходные процессы в , и установившиеся значения состояния могли быть записаны в . Переходные процессы начинаются из-за изменения либо состояния , либо изменения входных сигналов. Изменение значений на выходах происходит всегда на границе такта. Для корректной работы синхронного автомата изменения входных сигналов должны происходить в интервале (рисунок 4.1.) так, что бы время , было бы достаточным для завершения переходных процессов.

Рисунок 4.1.2 Структура такта.

В соответствии с каноническими уравнениями можно детализировать схему на рисунок 4.1.2. и представить Конечный Автомат в виде схемы на рисунок 4.3., где одна представлена как декомпозиция двух и .

Рисунок 4.3. Функции перехода , выхода и памяти в СЦА.


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

Память автомата.

Один двоичный разряд кода состояния запоминается триггером, обычно это – -триггер, который может находиться в составе регистра. Напомним поведение во времени -триггера с динамической синхронизацией (рисунок 4.4).

Рисунок 4.4.–триггер (функциональное обозначение и временные диаграммы)

Триггер выдает в течение такта значение, которое он «увидел» на -входе во время появления рабочего фронта сигнала на -входе. Таким образом,-триггер узнает об изменении сигнала на входе c задержкой, которая называется синхронизационной задержкой ( – на рисунок 4.1.). На изображении триггера (рисунок 4.4.) не показаны входы асинхронной установки, обычно необходимые и присутствующие в реальных изделиях.

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

Основные типы синхронных автоматов

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

  1. полностью определенный и частично-определенный;
  2. инициальный и неинициальный;

а также выделим некоторый класс - класс автоматов Мура.

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

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

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

Для реализации инициального автомата схема должна быть сконструирована так, чтобы начальное состояние фиксировалось (запоминалось) в до начала работы автомата.

Автомат Мура

Автомат Мура - синхронный автомат, у которого значения выхода определяются только состоянием автомата в тот же дискретный момент времени. При этом , вычисляющая выходное значение, не связана непосредственно с входными сигналами см. рисунок 4.5.

Рисунок 4.5. Автомат Мура ,

Поэтому момент изменения выходных сигналов зависит только от момента изменения сигнала синхронизации (рабочего фронта). О такой зависимости между входом и выходом принято говорить, что вход и выход “развязаны во времени”, или иначе - выход автомата “со сдвигом” зависит от входа.


Автомат Мили

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

В автомате Мили могут одновременно существовать выходные переменные, которые зависят от входных переменных, как со сдвигом, так и без сдвига, как, например, в схеме автомата, приведенной на рисунок 4.6.

Рисунок 4.6. Автомат Мили:

Переменная зависит только от состояния автомата, т.е. со сдвигом от всех входных переменных. Переменная зависит от переменной и состояния.

Способы описания автоматов

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

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

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

Список источников

  1. Новиков Ф.А. Дискретная математика для программистов:Учебное пособие для вузов / - 2-е изд. - СПб.; М.; Нижний Новгород: Питер, 2007. - 363[5] с.: ил. - (Учебник для вузов). - ISBN 5-94723-741-5.
  2. Иванов Б.Н. Дискретная математика. Алгоритмы и программы : Учебное пособие для вузов / - М.: Лаборатория Базовых Знаний, 2003. - 288 с.: ил. - (Технический университет). - ISBN 5-93208-093-0.
  3. Шапорев С.Д. Дискретная математика. Курс лекций и практич. занятий: Уч. пособие для вузов /- СПб.: БХВ-Петербург, 2006. - 396 с. : ил. - ISBN 5-94157-703-6.
  4. Акимов О.Е. Дискретная математика: логика, группы, графы / - 2-е изд., доп. - М.: Лаборатория Базовых Знаний, 2003. - 376 с.: ил. - (Технич. ун-т. Математика).
  5. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах: Учеб. пособие / - М.: Гелиос АРВ, 2003. - 231 с.: ил. - ISBN 5-85438-069-2.
  6. Плотников А.Д. Дискретная математика: Учебное пособие / - 2-е изд., испр. и доп. - М.: Новое знание, 2006. - 304 с.: ил. - ISBN 5-94735-105-6.
  7. Хаггарти Р. Дискретная математика для программистов : Пер. с англ. : Уч. пособие для вузов/ ред. пер. С. А. Кулешов,. - 2-е изд., доп. - М. Техносфера, 2005. - 399[1] с.: ил. - (Мир программирования) - ISBN 5-94836-016-4.
  8. Смыслова З.А. Дискретная математика: учебное пособие / Министерство образования Российской Федерации (М.), Томский государственный университет систем управления и радиоэлектроники (Томск), Кафедра автоматизации обработки информации - Томск: ТМЦДО, 2000. - 116 с.
  9. Смыслова З.А., Пермякова Н. В. Дискретная математика: Методические указания для выполнения практических работ для студентов специальности 230102 / Федеральное агентство по образованию, Томский государственный университет систем управления и радиоэлектроники - Томск: [б. и.], 2007. - 28 с.
  10. Пермякова Н. В. Спецглавы математики: учебное пособие / Министерство образования Российской Федерации, ТУСУР - Томск : ТМЦДО, 2000 - .Ч. 2: Теория графов: учебное пособие. - Томск: ТМЦДО, 2000. - 125 с.