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

Существуют три способа задания конечных автоматов:

· Табличный (матрицы переходов и выходов);

· Графический (с помощью графов);

· Аналитический (с помощью формул).

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

Табличный способ. Составляется таблица состояния автоматадля функции перехода – δ и функции выхода. При этом:

· столбцы таблицы соответствуют элементам входного алфавита X,

· строки таблицы соответствуют состояни­ям (элементы конечного множества Q).

Пересечению i-и строки и j-го столбца соответствует клетка (i, j), которая является аргументом функций 8 и λ автомата в момент, когда он находится в состоя­нии q i на его входе – слово x j , а в самой соответствующей клетке запишем значения функций 8 и λ. Таким образом, вся таблица соответствует множеству Q х X.

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

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

В матрице переходов на пересечении строки x k и столбца q r помещается значение функции перехода δ(q i , х) и функции выводов λ(q, х) . В ряде случаев обе таблицы объединяются в одну таблицу.

Графический способ.

Автомат задается с помощью графа, схемы, графика и др. Задание с помощью ориентированного гра­фа – более удобная и компактная форма описания автомата.

Граф автомата содержит

· Вершины, соответствующие состоянию q i ÎQ,

· Дуги, соединяющие вершины – переходы автомата из одного состояния в другое. На дугах принято указывать пары вход­ных и выходных сигналов – сигналов переходов.

Если автомат переходит из состояния q 1 в состояние q 2 под воз­действием нескольких входных сигналов, то на соответствующей дуге графа этот вариант будет представлен через дизъюнкцию. Для представления автомата используют двухполюсные графы с выде­ленными начальным и конечным состояниями.

Разработка шкалы «прибора для измерения емкости»

№	индикация	+	-	перегруз.	выкл.	┤
0	исх.сост.	1	0	0	0	нет
1	0	2	0	13	0	да
2	50	3	1	13	0	да
3	100	4	2	13	0	да
4	150	5	3	13	0	да
5	200	6	4	13	0	да
6	250	7	5	13	0	да
7	300	8	6	13	0	да
8	350	9	7	13	0	да
9	400	10	8	13	0	да
10	450	11	9	13	0	да
11	500	13	10	13	0	да
12	ОВ	0	0	0	0	нет
13	авария	0	0	0	0	нет

Рис.2.5. Граф шкалы прибора для измерения емкости

Заключение

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

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

В практической части была раскрыта тема, касающаяся шифраторов, дешифраторов, их назначения, а также были спроектированы электрические функциональные и электрические принципиальные схемы шифраторов и дешифраторов. Была раскрыта тема карт Карно. Также был разработан сегмент “b” семисегментного индикатора. Был разработан конечный автомат для шкалы прибора для измерения емкости, а также граф для него.

Баранов Виктор Павлович. Дискретная математика. Раздел 6. Конечные автоматы и формальные языки.

Лекция 31. Определение и способы задания конечного автомата. Задача синтеза. Элементарные автом а ты

Лекция 30. ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА.

ЗАДАЧА СИНТЕЗА. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ

План лекции:

1. Определение конечного автомата.

2. Способы задания конечного автомата.

1. Задача синтеза автоматов.
2. Элементарные автоматы.
3. Задача о полноте автоматного базиса.
4. Канонический метод синтеза автомата.

1. Определение конечного автомата

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

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

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

Работа автомата представляется следующим образом.

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

Дадим формальное определение автомата.

Конечным автоматом называют пятерку объектов

, (1)

где

входным алфавитом ; – одно из возможных состояний входа;

– конечное множество, называемое выходным алфавитом ; элеме н ты этого множества определяют возможные состояния выхода;

– конечное множество, называемое алфавитом внутренних состо я ний ;

– функция переходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие состояние;

– функция выходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие значение выхода.

Закон функционирования автомата: автомат изменяет свои состояния в соотве т ствии с функцией и вырабатывает выходные сигналы в соответствии с фун к цией:

1. Способы задания конечного автомата

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

Пример 1. Зададим автомат следующим образом: , .Функцию определим с помощью таблицы переходов, а функцию – с помощью таблицы выходов .

Таблица 1. Таблица переходов Таблица 2. Таблица выходов

Вход	Состояние

Вход	Состояние

Если известна последовательность сигналов на входе автомата, то таблицами пер е ходов и выходов однозначно определяется выходная последовательность.

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

| | |

Рис.1 Диаграмма переходов-выходов

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

Автомат находится в состоянии 1, если при сложении предыдущих разрядов возн и кает перенос, и в состоянии 0 – в противном случае. Диаграмма переходов-выходов пок а зана на рис. 2.

00|0 11|1 01|0

01|1 10|0

10|1 00|1 11|1

Рис. 2

1. Задача синтеза автоматов

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

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

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

Пусть – конечное множество из элементов, а – множ е ство двоичных слов длины, где. Произвольное инъективное отображение будем называть кодированием множества двоичными словами.

Произведем кодирование алфавитов для произвольного автомата:

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

(2)

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

… …

Рис. 3

Переход к структурному автомату обеспечивает два важных для синтеза преимущ е ства.

1  . Совместимость входов и выходов, так как через них передается двоичная и н формация. Мы не будем давать общее определение схемы из структурных автоматов – оно аналогично СФЭ.

2  . Запишем соотношения (2) в «координатах»:

(3)

Из (3) следует, что закон функционирования структурного автомата задается с и стемой булевых функций .

1. Элементарные автоматы

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

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

Перейдем к автоматам с двумя состояниями. Пусть автомат имеет один двоичный вход и один двоичный выход, совпадающий с внутренним состоянием: :

Рис. 4.

Для задания автомата, показанного на рис. 4, достаточно задать только таблицу п е реходов:

Таблица 3

Вход	Состояние

Вместо звездочек нужно поставить 0 и 1. Это можно сделать 16 способами, однако, не все они приемлемы. Допустим, например, что в первом столбце таблицы 3 оба элеме н ты нули. Такой автомат, оказавшись в состоянии 0, более из него не выйдет, то есть будет работать как функциональный элемент. Анализ аналогичный ситуаций показывает, что для того чтобы получился автомат, не сводящийся к автомату без памяти, надо потреб о вать, чтобы в каждом столбце таблицы 3 встречались и ноль и единица. Таких таблиц вс е го ч е тыре.

Таблица 4 Таблица 5

Вход	Состояние
					Вход	Состояние

Таблица 6 Таблица 7

Вход	Состояние

Вход	Состояние

Имеем только два простейших автомата, так как 7 получается из 4, а 6 из 5 путем инверсии внутренних состояний.

Автомат, задаваемый таблицей 4, называется задержкой или -триггером :

то есть этот автомат задерживает сигнал на один такт.

Автомат, задаваемый таблицей 5, называется триггером со счетным входом или -триггером . Состояние автомата меняется на противоположное, если на вход поступает 1, и остается без изменения, если на вход поступает 0:

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

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

Рис. 5.

1. Задача о полноте автоматного базиса

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

Усилия математиков для получения аналога теоремы Поста для автоматов не уве н чались успехом. В 1964 г. М.И. Кратко доказал несуществование алгоритма для определ е ния полноты системы. В этом случае представляют интерес варианты теоремы о полноте с дополнительными предположениями о системе. Рассмотрим наиболее популярный из них.

Теорема. Система автоматов, содержащая полный набор ФЭ и - триггер (или -триггер) является полной.

Доказательство. Рассмотрим произвольный автомат, заданный соотнош е ниями (2), и опишем его схему из указанных автоматов, называемую канонической структурой (рис. 6) .

Схема состоит из двух частей.

…

…

…

Рис. 6.

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

, …,

то это означает, что автомат находится в состоянии.

Правая половина называется комбинационной частью и представляет СФЭ. Входы этой схемы:

1. двоичное слово – входной сигнал автомата;
2. двоичное слово – текущее внутреннее состояние автомата.

Выходы:

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

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

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

, .

Используемые в канонической схеме -триггеры или -триггеры обладают сл е дующим свойством: для любой пары состояний существует входной сигнал, пер е водящий автомат из состояния в состояние. Обозначим этот сигнал через. Для -триггера, так как состояние, в которое устанавливается -триггер, равно входному сигналу. Для -триггера: при на вход надо п о дать 0, чтобы состояние не изменилось; при – 1, чтобы триггер «перевернулся».

Итак, или в векторной форме

Выразим из закона функционирования автомата (2). Тогда

Теорема доказана.

1. Канонический метод синтеза автомата

Рассмотрим этот метод на конкретном примере.

Пример. На конвейере, по которому двигаются детали двух типов и, устано в лен автомат, задачей которого является такая сортировка деталей, чтобы после прохожд е ния мимо автомата они образовывали группы. Неподходящую деталь автомат ста л кивает с конвейера. Требуется построить схему такого автомата, используя -триггер и элементы «И», «ИЛИ», «НЕ».

Синтез автомата разбивается на следующие этапы.

1  . Построение абстрактного автомата.

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

| | |

Рис. 7.

2  . Кодирование алфавитов.

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

Вход Выход Состояние

3  . Построение канонической структуры автомата.

Каноническая структура разрабатываемого автомата показана на рис. 8.

Рис. 8.

Найдем зависимости выходов СФЭ, от переменных сначала в табличном виде (таблица 8), по к о торым далее построим формулы

, .

Таблица 8

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

4  . Представление функций выхода автомата и функций управления памятью фо р мулами.

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

5  . Реализация СФЭ и окончательная схема автомата (рис. 9).

Рис. 9.

СФЭ

СФЭ

НЕ

ИЛИ

Баранов Виктор Павлович. Дискретная математика. Раздел 6. Конечные автоматы и формальные языки.

Лекция 31. Определение и способы задания конечного автомата. Задача синтеза. Элементарные автоматы

Лекция 30. ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА.

ЗАДАЧА СИНТЕЗА. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ

План лекции:

1. Определение конечного автомата.

2. Способы задания конечного автомата.

1. Задача синтеза автоматов.
2. Элементарные автоматы.
3. Задача о полноте автоматного базиса.
4. Канонический метод синтеза автомата.

1. Определение конечного автомата

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

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

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

Работа автомата представляется следующим образом.

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

Дадим формальное определение автомата.

Конечным автоматом называют пятерку объектов

– конечное множество, называемое входным алфавитом; – одно из возможных состояний входа;

– конечное множество, называемое выходным алфавитом; элементы этого множества определяют возможные состояния выхода;

– конечное множество, называемое алфавитом внутренних состояний;

– функция переходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие состояние;

– функция выходов автомата: ; эта функция каждой паре «вход-состояние» ставит в соответствие значение выхода.

Закон функционирования автомата: автомат изменяет свои состояния в соответствии с функцией и вырабатывает выходные сигналы в соответствии с функцией:

1. Способы задания конечного автомата

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

Пример 1. Зададим автомат следующим образом: , .Функцию определим с помощью таблицы переходов, а функцию – с помощью таблицы выходов.

Таблица 1. Таблица переходов Таблица 2. Таблица выходов

	Состояние

	Состояние

Если известна последовательность сигналов на входе автомата, то таблицами переходов и выходов однозначно определяется выходная последовательность.

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

Рис.1 Диаграмма переходов-выходов

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

Автомат находится в состоянии 1, если при сложении предыдущих разрядов возникает перенос, и в состоянии 0 – в противном случае. Диаграмма переходов-выходов показана на рис. 2.

1. Задача синтеза автоматов

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

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

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

Пусть – конечное множество из элементов, а – множество двоичных слов длины, где. Произвольное инъективное отображение будем называть кодированием множества двоичными словами.

Произведем кодирование алфавитов для произвольного автомата:

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

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

Переход к структурному автомату обеспечивает два важных для синтеза преимущества.

1. Совместимость входов и выходов, так как через них передается двоичная информация. Мы не будем давать общее определение схемы из структурных автоматов – оно аналогично СФЭ.

2. Запишем соотношения (2) в «координатах»:

Из (3) следует, что закон функционирования структурного автомата задается системой булевых функций.

1. Элементарные автоматы

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

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

Перейдем к автоматам с двумя состояниями. Пусть автомат имеет один двоичный вход и один двоичный выход, совпадающий с внутренним состоянием: :

Для задания автомата, показанного на рис. 4, достаточно задать только таблицу переходов:

Таблица 3

	Состояние

Вместо звездочек нужно поставить 0 и 1. Это можно сделать 16 способами, однако, не все они приемлемы. Допустим, например, что в первом столбце таблицы 3 оба элементы нули. Такой автомат, оказавшись в состоянии 0, более из него не выйдет, то есть будет работать как функциональный элемент. Анализ аналогичный ситуаций показывает, что для того чтобы получился автомат, не сводящийся к автомату без памяти, надо потребовать, чтобы в каждом столбце таблицы 3 встречались и ноль и единица. Таких таблиц всего четыре.

Таблица 4 Таблица 5

	Состояние
					Состояние

Таблица 6 Таблица 7

	Состояние

	Состояние

Имеем только два простейших автомата, так как 7 получается из 4, а 6 из 5 путем инверсии внутренних состояний.

Автомат, задаваемый таблицей 4, называется задержкой или -триггером:

то есть этот автомат задерживает сигнал на один такт.

Автомат, задаваемый таблицей 5, называется триггером со счетным входом или -триггером. Состояние автомата меняется на противоположное, если на вход поступает 1, и остается без изменения, если на вход поступает 0:

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

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

1. Задача о полноте автоматного базиса

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

Усилия математиков для получения аналога теоремы Поста для автоматов не увенчались успехом. В 1964 г. М.И. Кратко доказал несуществование алгоритма для определения полноты системы. В этом случае представляют интерес варианты теоремы о полноте с дополнительными предположениями о системе. Рассмотрим наиболее популярный из них.

Теорема. Система автоматов, содержащая полный набор ФЭ и -триггер (или -триггер) является полной.

Доказательство. Рассмотрим произвольный автомат, заданный соотношениями (2), и опишем его схему из указанных автоматов, называемую канонической структурой (рис. 6).

Схема состоит из двух частей.

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

то это означает, что автомат находится в состоянии.

Правая половина называется комбинационной частью и представляет СФЭ. Входы этой схемы:

1. двоичное слово – входной сигнал автомата;
2. двоичное слово – текущее внутреннее состояние автомата.

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

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

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

Используемые в канонической схеме -триггеры или -триггеры обладают следующим свойством: для любой пары состояний существует входной сигнал, переводящий автомат из состояния в состояние. Обозначим этот сигнал через. Для -триггера, так как состояние, в которое устанавливается -триггер, равно входному сигналу. Для -триггера: при на вход надо подать 0, чтобы состояние не изменилось; при – 1, чтобы триггер «перевернулся».

Итак, или в векторной форме

Выразим из закона функционирования автомата (2). Тогда

Теорема доказана.

1. Канонический метод синтеза автомата

Рассмотрим этот метод на конкретном примере.

Пример. На конвейере, по которому двигаются детали двух типов и, установлен автомат, задачей которого является такая сортировка деталей, чтобы после прохождения мимо автомата они образовывали группы. Неподходящую деталь автомат сталкивает с конвейера. Требуется построить схему такого автомата, используя -триггер и элементы «И», «ИЛИ», «НЕ».

Синтез автомата разбивается на следующие этапы.

1. Построение абстрактного автомата.

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

2. Кодирование алфавитов.

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

Вход Выход Состояние

3. Построение канонической структуры автомата.

Каноническая структура разрабатываемого автомата показана на рис. 8.

Найдем зависимости выходов СФЭ, от переменных сначала в табличном виде (таблица 8), по которым далее построим формулы

Таблица 8

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

4. Представление функций выхода автомата и функций управления памятью формулами.

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

5. Реализация СФЭ и окончательная схема автомата (рис. 9).

ОПРЕДЕЛЕНИЕ И СПОСОБЫ ЗАДАНИЯ КОНЕЧНОГО АВТОМАТА. ЗАДАЧА СИНТЕЗА. ЭЛЕМЕНТАРНЫЕ АВТОМАТЫ

ПЛАН ЛЕКЦИИ

1. Табличный способ

2. Графический способ задания автомата

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d , l } , т.е. необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходов l . При этом среди множества A = {a 0 ,a 1 ,…, a n } необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

1. Табличный способ

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

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

x j \a j
	d (a 0 ,x 1)		d (a n ,x 1)
x m	d (a 0 ,x m)		d (a n ,x m )

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

x j \a j
	l (a 0 ,x 1)		l (a n ,x 1)
x m	l (a 0 ,x m)		l (a n ,x m )

Строки этих таблиц соответствуют входным сигналам x (t ), а столбцы – состояниям. На пересечении столбца a i и строки x j в таблице переходов ставится состояние a s = d [ a i ,x j ], в которое автомат перейдет из состояния a i под воздействием сигнала x j ; а в таблице выходов – соответствующий этому переходу выходной сигнал y g = l [ a i ,x j ].

Совмещенная таблица переходов и выходов автомата Мили:

x j \a i
	d (a 0 ,x 1)/ l (a 0 ,x 1)		d (a n ,x 1)/ l (a n ,x 1)
x m	d (a 0 ,x m)/ l (a 0 ,x m)		d (a n ,x m )/ l (a n ,x m )

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

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

Отмеченная таблица переходов автомата Мура :

y g	l (a 0)		l (a n)
x j \a c
	d (a 0 ,x 1)		d (a n ,x 1)
x m	d (a 0 ,x m)		d (a n ,x m )

Автомат Мили

x j \a i
	a 1 /y 1	a 2 /y 3	А 3 /y 2	a 0 /y 1
	a 0 /y 2	a 0 /y 1	A 3 /y 1	a 2 /y 3

Автомат Мура

x j \x j

В этой таблице каждому столбцу приписан, кроме состояния a i , еще и выходной сигнал y (t ) = l (a (t )), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Приведем примеры табличного задания автоматов Мили и Мура :

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

Для автомата Мили:Для автомата Мура :

x 1 x 2 x 2 x 2 x 1 …x 1 x 2 x 2 x 2 x 1 …

a 0 a 1 a 0 a 0 a 0 a 1 a 0 a 2 a 4 a 1 a 4

y 1 y 1 y 2 y 2 y 1 y 2 y 1 y 2 y 1 y 2

2. Графический способ задания автомата (задание автомата с помощью графа)

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s , если в автомате имеется переход из a i в a s , т.е. a s =d (a i , x j ). В автомате Мили дуга отмечается входным сигналом x j , вызвавшим переход, и выходным сигналом y g , который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

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

Конечным автоматом называется система Y, Q>, в которой X и Y являются конечными входным и выходным алфавитами, Q - конечным множеством внутренних состояний, Y(x, q) - функцией переходов и Q(x,q) - функцией выходов.

Как указывалось ранее, Y(x,q) задает порядок преобразования входных символов и состояния автомата на предыдущем такте в состояние на последующем, a Q(x,q) - преобразования входных символов и состояния автомата на текущем такте в выходной символ. Если q 0 - начальное состояние автомата, а i - номер такта, то его работа описывается системой:

Данные соотношения получили название системы канонических уравнений конечного автомата. Пользуясь ими можно, начиная с q 0 , последовательно находить все последующие состояния автомата и выходные символы.

Выделяются два типа автоматов - инициальные и неинициальные. В инициальных автоматах начальное состояние фиксировано (т.е. они всегда начинают работать из одного и того же состояния q 0). В неинициальных автоматах в качестве начального состояния может быть выбрано любое из множества Q ; этим выбором определяется дальнейшее поведение автомата.

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

В табличном способе автоматные функции задаются двумя конечными таблицами, именуемыми соответственно матрицей переходов и матрицей выходов. В этих таблицах строки обозначаются буквами входного алфавита, а столбцы - буквами внутреннего алфавита (символами, кодирующими внутреннее состояние автомата). В матрице переходов на пересечении строки (x k) и столбца (q r) помещаются значения функции Y (q r , x k), а в матрице выходов - значения функции Q(q r , x k).