Автоматы можно рассматривать как механизмы, состоящие из:
блока управления, который может пребывать в различных состояниях ( S внутренний алфавит);
входного канала;
выходного канала.
Входной канал считывает входные сигналы ( Х ) из внешней среды. Выходной канал выдает выходные сигналы ( Y ) во внешнюю среду. Работа автомата протекает в дискретные такты времени t =1,2,3,…. По команде в некотором такте времени блок управления установлен в состоянии и входной канал воспринимает , тогда в этом же такте в выходной канал выдается символ , а к следующему такту +1 блок управления перейдет в состояние .
Определение. К.Д.А. называется система , где — алфавит состояний, – входной алфавит, – выходной алфавит. Множества S , X , Y – конечные.
Если в автомате выделено одно состояние , называемое начальным (обычно ), то автомат называется инициальным .
4.2 Способы задания автоматов.
Таблица переходов–выходов.
С помощью орграфов. Вершины граф означают состояния, а дуги – переходы между ними. Из каждой вершина исходит k дуг. Из вершины проводится дуга в вершину в том и только в том случае, когда для некоторого .
Этой дуге приписывается пометка :
Начальное состояние в инициальном автомате помечается символом . Описанный таким образом орграф с пометками называется диаграммой Мура.
С помощью канонических уравнений:
в момент t =1 автомат находится в начальном состоянии . В каждый момент t =1,2,3,… дискретного времени автомат, находясь в некотором состоянии s ( t ) из множества S , под действием входного сигнала выдает выходной сигнал из множества Y , согласно функции выходов l , а затем меняет свое состояние на s ( t +1) согласно функции переходов d .
Для определения множества состояний автомата необходимо уяснить содержательный смысл и назначение понятия состояния.
После преобразования входного сигнала в выходной его значение к следующему такту времени теряется. Иначе говоря, в любой тактовый момент t в устройстве нет информации о сигналах в предыдущие моменты, то есть о значениях , , ,… . Поэтому, если при вычислении значения функции переходов и выходов по формуле необходима информация об этих тактовых моментах, то ее нужно каким-либо образом «запомнить». В этом и состоит содержательное назначение состояний. Состояния – это вспомогательные объекты, которые подбираются таким образом, чтобы в совокупности с входным значением однозначно определить выходное значение . Обычно состояния кодируют ту информацию, которая поступила до момента t .
Пример. Построить таблицу переходов–выходов К.Д.А, реализующего функцию:
Чтобы на любом, отличном от первого, такте иметь информацию о , введем два следующих состояния:
И –начальное состояние.
Построим таблицу переходов–выходов:
Для нарисуем диаграмму Мура:
И дополним таблицу переходов–выходов:
4.3 Эквивалентные состояния. Минимизация к.д.а.
Определение. Две диаграммы Мура называются изоморфными , если они могут быть превращены одна в другую переобозначением вершин.
Определение. Два автомата называются изоморфными , если их диаграммы Мура изоморфны.
Рассмотрим два автомата и с одинаковыми входным и выходным алфавитами.
Определение. Состояния и называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого входного слова х результат работы автомата такой же, как и для .
В частном случае, когда = , то речь идет о неотличимых состояниях одного автомата.
Определение. Автоматы и называются неотличимыми (эквивалентными) тогда и только тогда, когда для любого состояния найдется эквивалентное ему состояние и обратно.
Неотличимые автоматы осуществляют одно и то же отображение входных слов в выходные.
Определение. Автомат А называется приведенным , если в нем нет эквивалентных (неразличимых) состояний.
Число состояний в приведенном автомате минимально . Для любого автомата существует эквивалентный ему приведенный автомат А . Процедура нахождения такого автомата называется минимизацией автомата .
4.4 Алгоритм минимизации конечного автомата.
Шаг 1 : два состояния s и t относим в один класс , если для любого входного символа x значение функции выхода s совпадает со значениями функции выхода t . В результате получим r классов:
Шаг k : два состояния s и t из одного класса , полученного на предыдущем шаге, относим в один класс , если для любого значения входного символа значения функций состояний принадлежат одному и тому же классу из предыдущего шага. Если шаг k не изменяет разбиения, то процесс останавливается. Доопределяем функции перехода и выхода и строим таблицу переходов –выходов.
Шаг 1: Первое, третье и четвертое состояния отнесем в один класс состояний, а второе, пятое и шестое – в другой:
Шаг 2: Выпишем значения функции переходов для состояний из класса :
Видно, что 1 и 3-е состояния относим в один класс этого шага , а четвертое состояние – в другой . Проанализировав аналогичным образом значения функции выходов для состояний из класса , видим:
; ; , т.е. все они остаются в одном классе. В результате получим разбиение на классы:
Шаг 3: ; ; . Дальнейшего разбиения классов не происходит, поэтому процесс останавливается. Класс назовем состоянием , класс состояний назовем состоянием , а класс – состоянием .
Построим таблицу переходов–выходов:
Построенный автомат – минимальный.
4.5 Каноническая таблица. Канонические уравнения.
Реализация К.Д.А. осуществляется на основе канонических уравнений, которые находятся с помощью канонической таблицы. Каноническая таблица строится следующим образом по таблице переходов–выходов или диаграмме Мура.
Аргументы функций l и d находятся в столбцах слева, а справа – их значения.
— кодирование состояний и выходов автомата и сложность комбинационных схем;
Видео:Математическое определение конечного автомата. Душкин объяснитСкачать
— обеспечение устойчивости функционирования цифровых автоматов;
Видео:Кружок - группа A - конечные автоматы, автомат КМПСкачать
— гонки в автоматах;
Видео:Лекция 299. Графы для цифровых автоматовСкачать
— методы устранения гонок в автоматах и др.
Видео:Решение систем уравнений методом подстановкиСкачать
1.Основные понятия. Канонический метод структурного синтеза автоматов. Теорема Глушкова о структурной полноте
Вслед за этапом абстрактного синтеза автоматов, заканчивающимся минимизацией числа состояний, следует этап структурного синтеза, цепью которого является построение схемы, реализующей автомат из логических элементов заданного типа.
Если абстрактный автомат был лишь математической моделью дискретной системы, то в структурном автомате учитывается структура входных и выходных сигналов автомата, а также его внутреннее устройство на уровне структурных схем. Структурным синтезом занимается структурная теория автоматов, основной задачей которой является нахождение общих приемов построения структурных схем автоматов на основе композиции элементарных автоматов, принадлежащих к заранее заданному конечному числу типов.
Под композицией элементарных автоматов в общем случае понимается следующее.
Пусть заданы элементарные автоматы S1 . Sk . Произведем объединение элементарных автоматов в систему совместно работающих автоматов. Введем в рассмотрение некоторое конечное множество узлов, называемых внешними входными и внешними выходными узлами. Эти узлы отличаются от узлов рассматриваемых элементарных автоматов, которые носят название внутренних. Композиция автомата состоит в том, что в полученной системе элементарных автоматов S1 . Sk и внешних узлов производится отождествление некоторых узлов (как внешних, так и внутренних). С точки зрения совместной работы системы автоматов смысл операции отождествления узлов состоит в том, что элементарный сигнал, попадающий на один из узлов, входящих в множество отождествляемых между собой узлов, попадает тем самым на все узлы этого множества, После проведенных отождествлений узлов система автоматов превращается в так называемую схему (сеть) автоматов. Будем считать, что автоматы, входящие в схему автоматов, работают совместно, если в каждый момент автоматного времени на все внешние входные узлы подается набор входных сигналов (структурный входной сигнал схемы) и со всех внешних выходных узлов снимается набор выходных сигналов (структурный выходной сигнал).
В структурной теории как входные так и выходные каналы считаются состоящими из элементарных входных (выходных) каналов. По всем элементарным входным (выходным) каналам могут передаваться только элементарные сигналы.
Рисунок 1- Структурный автомат
Набор возможных значений сигналов, подаваемых на один внешний входной (выходной) узел, называется структурным входным (выходным) алфавитом автомата. Алфавит должен быть конечным.
Входной и выходной сигналы задаются конечными упорядоченными наборами элементарных сигналов, называемыми векторами, а составляющие их элементарные сигналы — компоненты векторов. Число компонентов вектора — это размерность алфавита.
Структурный входной алфавит, размерность которого равна трем:
Векторное представление входных и выходных сигналов называется структурным входным выходным сигналом, соответственно.
Предполагается, что все входящие в композицию автоматы имеют один и тот же структурный алфавит и работают в одном и том же автоматном времени. В настоящее время наиболее распространенным структурным алфавитом является двоичный, что объясняется простотой его представления в современных элементах и приборах. Кроме того, для двоичного алфавита наиболее разработан аппарат булевых функций, позволяющий производить многие операции над схемой формально. Поэтому в дальнейшем при решении задач структурного синтеза автоматов будет использоваться в основном двоичный, структурный алфавит.
Предположим, что в каждый момент автоматного времени структурный выходной сигнал схемы однозначно определяется поступившей к этому времени конечной последовательностью структурных входных сигналов, начальными состояниями входящих в схему автоматов и сделанными при построении схемы отождествлениями узлов. В этом случае построенную схему будем рассматривать как некоторый автомат S, а саму схему назовем структурной схемой этого автомата.
Построенный таким образом автомат S есть результат композиции элементарных автоматов S1 . Sk . В отличие от абстрактного C-автомата, имеющего один входной и два выходных канала, на которые поступают сигналы во входном и выходных алфавитах автомата, структурный автомат имеет входные и выходные каналы, на которых появляются сигналы в структурном алфавите автомата. В случае двоичного алфавита каждый входной и выходные сигналы абстрактного автомата могут быть закодированы векторами различной длины соответственно, компоненты которых принимают два значения — нуль и единицу.
На этапе структурного синтеза предварительно выбираются элементарные автоматы, из которых затем путем их композиции строится структурная схема полученного на этапе абстрактного синтеза автомата Мили, Мура или C-автомата. Если решение задачи структурного синтеза существует, говорят, что заданная система автоматов структурно полна.
В настоящее время нет сколько-нибудь эффективных методов (существенно более простых, чем метод перебора всех вариантов) решения основной задачи структурного синтеза при любом наборе структурно полных систем элементарных автоматов. Поэтому обычно применяется так называемый канонический метод структурного синтеза, при котором используются элементарные автоматы некоторого специального вида: автоматы с памятью, имеющие более одного состояния, и автоматы без памяти — с одним состоянием. Автоматы первого класса носят название элементов памяти, а автоматы второго класса — комбинационных или логических элементов.
Теоретическим обоснованием канонического метода структурного синтеза автоматов является доказанная в теорема о структурной полноте (теорема Глушкова):
Всякая система элементарных автоматов, которая содержит автомат Мура с нетривиальной памятью, обладающий полной системой переходов и полной системой выходов, и какую-либо функционально полную систему логических элементов, является структурно полной.
Существует общий конструктивный прием (канонический метод структурного синтеза), позволяющий в рассматриваемом случае свести задачу структурного синтеза произвольных автоматов к задаче синтеза комбинационных схем.
Результатом канонического метода структурного синтеза является система логических уравнений, выражающая зависимость выходных сигналов автомата (функции выходов автомата) и сигналов, подаваемых на входы запоминающих элементов, от сигналов, приходящих на вход всего автомата в целом, и сигналов, снимаемых с выхода элементов памяти (функции возбуждения элементов памяти автомата). Эти уравнения называютсяканоническими.
Для правильной работы схем, очевидно, нельзя разрешать, чтобы сигналы на входе запоминающих элементов непосредственно участвовали в образовании выходных сигналов, которые по цепям обратной связи подавались бы в тот же самый момент времени на эти входы. В связи с этим запоминающими элементами должны быть не автоматы Мили, а автоматы Мура (см. уравнения функционирования этих автоматов).
Таким образом, структурно полная система элементарных автоматов должна содержать хотя бы один автомат Мура. В то же время для синтеза любых автоматов с минимальным числом элементов памяти необходимо в качестве таких элементов выбирать автоматы Мура, имеющие полную систему переходов и полную систему выходов — так называемые полные автоматы.
Рассмотрим полноту автоматов памяти на примере автомата Мура. (табл. 1.) Полнота системы переходов означает, что для любой пары состояний (am ,…,аs ) автомата найдется входной сигнал, переводящий первый элемент этой пары am во второй — as т. е. в таком автомате в каждом столбце таблицы переходов должны встречаться все состояния автомата. Полнота системы выходов автомата Мура состоит в том, что каждому состоянию автомата поставлен в соответствие свой особый выходной сигнал, отличный от выходных сигналов других состояний.
У
y1
y2
y3
AX
x1
x2
x3
a1
a1
a2
a3
a2
a3
a1
a2
a3
a2
a3
a1
Очевидно, что в таком автомате число выходных сигналов равно числу состояний автомата. Вместе с предыдущим утверждением это приводит к тому, что в автомате Мура с полной системой выходов можно отождествить состояния автомата с его выходными сигналами. В связи с этим в автоматах памяти мы будем использовать одни и те же обозначения и для состояний, и для выходных сигналов, т. е. отмеченная таблица переходов в автоматах Мура с полной системой выходов превращается просто в таблицу переходов. Автомат Мура в табл. 1. удовлетворяет условиям полноты системы переходов и выходов.
Наличие функционально полной системы логических элементов позволяет реализовать булеву функцию любой степени сложности.
После выбора элементов памяти и кодирования состояний синтез структурного автомата сводится к синтезу комбинационной схемы, реализующей канонические уравнения.
Автомат памяти также можно рассматривать на абстрактном и структурном уровнях. Абстрактный автомат памяти имеет один входной и один выходной каналы. При переходе от абстрактного автомата к структурному автомату входные и выходные сигналы должны быть закодированы соответствующими двоичными наборами.
Видео:Алексеев В. Б. - Дискретная математика - Эксперименты с автоматамиСкачать
2.Основные этапы канонического метода структурного синтеза
В каноническом методе структурного синтеза можно выделить несколько основных этапов:
1. Кодирование алфавитов автомата.
2. Выбор элементов памяти.
3. Выбор функционально полной системы логических элементов.
4. Запись и минимизация канонических уравнений.
5. Построение функциональной схемы автомата.
Исходными данными для начала работы данного метода являются абстрактный цифровой автомат с памятью, заданный таблицей переходов и выходов. Рассмотрим подробнее каждый из этапов канонического метода.
2.1 Кодирование алфавитов автомата
На структурном уровне каждая буква входного алфавита xХ, каждая буква выходного алфавита yY и каждая буква алфавита состояний аА кодируется двоичными векторами (двоичными наборами), число компонент которых определяется следующим образом:
где int — ближайшее большее целое число.
|Х|, |У|, |А| — мощность алфавита входного, выходного и состояний, соответственно. Мощностью алфавита называется количество различных символов входящих в этот алфавит.
Процесс замены буква алфавита (X, У, А) абстрактного автомата двоичными векторами носит название кодирования и описывается таблицами кодирования. Таблица кодирования имеем следующий вид: в левой части перечисляются все символы абстрактного алфавита, а в правой — соответствующие им двоичные векторы.
Х, каждая буква выходного алфавита y
