Пример: синтез автомата Мили

1.Задание

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

Таблица 1

Входные слова	Выходные слова

 

2.Получение автоматного алфавитного отображения информации

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

 

Таблица 2

Входные слова	Выходные слова

 

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

Таблица 3

Входные слова	Выходные слова

 

 

3.Построение формализованного описания работы автомата

По табл.3 строим граф и таблицу переходов – выходов. В задании необходимо синтезировать автомат Мили, т.е. каждая последняя буква входного слова должна переводить автомат в начальное состояние. При построении графа необходимо использовать минимальное число внутренних состояний автомата, рис.1.

Рис.1 Граф функционирования автомата Мили

Строим таблицу поведения автомата Мили, табл.4.

 

 

Таблица 4

Текущее состояние q(t)	Символы входного алфавита
				–
			–	–
			–

 

4. Построение кодированной таблицы переходов и выходов автомата

Закодируем символы входного алфавита, табл. 5.1.

Таблица5.1

 

Закодируем символы выходного алфавита, табл. 5.2.

 

Таблица 5.2

 

Закодируем символы выходного алфавита, табл. 5.3.

 

Таблица 5.3

 

 

По полученному графу и табл.4 строим кодированную таблицу переходов и выходов автомата, табл.6.

 

 

Таблица 6

	Входы	Q(t)	Q(t+1)	Выходы
	х1	х2	z1	z2	z1	z2	y1	y2
a1									q0(t)
a2
a3
a1									q1(t)
a2
a1									q2(t)
a2
a3
a1									q3(t)
a2

 

5. Определение и минимизация функций выходов автомата

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

Карта Карно для функции выхода y_1.

В результате минимизации получаем

Карта Карно для функции выхода y_2.

В результате минимизации получаем

6. Определение и минимизация функций переходов для заданных типов триггеров

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

Если предполагается использовать триггеры типа Е (RS) и D, то для них таблицы переходов имеют следующий вид, табл. 7.

Таблица 7

Q(t) Q(t+1)	D	R(E)	S(E)
0 0		*
0 1
1 0
1 1		*

 

 

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

Пусть триггер D используется для z₁(t+1)

Тогда D=

Если триггер Е (RS) используется для z , то, построив таблицу переходов, после минимизации с помощью карты Карно для входа R имеем R=

 

Построив таблицу переходов триггера Е (RS) для входа S, после минимизации с помощью карты Карно для входа S имеем:

7. Преобразование функций автомата в заданный базис

Пусть задан базис И, ИЛИ, НЕ. В этом случае дополнительного преобразования не требуется.

8. Введение сигналов синхронизации и установки в начальное состояние автомата

Сигнал синхронизации С вводится конъюнктивно

R=

9. Схема электрическая функциональная

 

 

Список литературы

а ) основная литература

1. Сулимов Ю.И. Электронные промышленные устройства [Электронный ресурс]: учебное пособие/ Сулимов Ю.И.— Электрон. текстовые данные.— Томск: Эль Контент, Томский государственный университет систем управления и радиоэлектроники, 2012.– 126 c. Режим доступа: http://www.iprbookshop.ru/14000 - ЭБС «IPRbooks»

б) дополнительная литература

1. Карпов, Ю.Г. Теория автоматов.: Учеб./ Карпов Ю.Г. – СПб.: Питер, 2003.– 208 с.: ил
2. Теория автоматов: Курс лекций./ Составитель Данилов Ю.В. – Сарапул, 2014.
3. Теория автоматов. Лабораторный практикум для студентовнаправления 230100.62 «Информатика и вычислительная техника»: Учеб.-методическое пособие./ Составитель Данилов Ю.В. – Сарапул, 2014.–45с.
4. Методические указания для проведения практических занятий по дисциплине «Теория автоматов» для направления 230100 «Информатика и вычислительная техника»/ Составитель Данилов Ю.В. – Сарапул: СПИ, 2014. – 31 с.

5. Савельев А.Я. Прикладная теория цифровых автоматов: Учеб. для вузов М. – ВШ., 2005