Пример: синтез автомата Мили
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. Определение и минимизация функций выходов автомата
Используя кодированную таблицу переходов и выходов автомата, заполним карты Карно для функций выходов и минимизируем их.
Карта Карно для функции выхода y1.
В результате минимизации получаем
Карта Карно для функции выхода y2.
В результате минимизации получаем
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 используется для z1(t+1)
Тогда D= 
Если триггер Е (RS) используется для z 
, то, построив таблицу переходов, после минимизации с помощью карты Карно для входа R имеем R= 
Построив таблицу переходов триггера Е (RS) для входа S, после минимизации с помощью карты Карно для входа S имеем:
7. Преобразование функций автомата в заданный базис
Пусть задан базис И, ИЛИ, НЕ. В этом случае дополнительного преобразования не требуется.
8. Введение сигналов синхронизации и установки в начальное состояние автомата
Сигнал синхронизации С вводится конъюнктивно
R= 
9. Схема электрическая функциональная
Список литературы
а)основная литература
1. Сулимов Ю.И. Электронные промышленные устройства [Электронный ресурс]: учебное пособие/ Сулимов Ю.И.— Электрон. текстовые данные.— Томск: Эль Контент, Томский государственный университет систем управления и радиоэлектроники, 2012.– 126 c. Режим доступа: http://www.iprbookshop.ru/14000 - ЭБС «IPRbooks»
б) дополнительная литература
- Карпов, Ю.Г. Теория автоматов.: Учеб./ Карпов Ю.Г. – СПб.: Питер, 2003.– 208 с.: ил
- Теория автоматов: Курс лекций./ Составитель Данилов Ю.В. – Сарапул, 2014.
- Теория автоматов. Лабораторный практикум для студентовнаправления 230100.62 «Информатика и вычислительная техника»: Учеб.-методическое пособие./ Составитель Данилов Ю.В. – Сарапул, 2014.–45с.
- Методические указания для проведения практических занятий по дисциплине «Теория автоматов» для направления 230100 «Информатика и вычислительная техника»/ Составитель Данилов Ю.В. – Сарапул: СПИ, 2014. – 31 с.
5. Савельев А.Я. Прикладная теория цифровых автоматов: Учеб. для вузов М. – ВШ., 2005