КУРСОВАЯ РАБОТА
по дисциплине «Теория Автоматов »
на тему «Синтез цифрового автомата »
Выполнил студент
Группы Б06-781-1з _______________ Е.А. Маслов
(шифр группы) (подпись, дата) (И.О. Фамилия)
Руководитель
Доцент К.Т.Н. Ю.В. Данилов
(должность, звание) (И.О. Фамилия)
руководителя
Рецензия:
степень достижения поставленной цели работы__________________________________
полнота разработки темы_____________________________________________________
уровень самостоятельной работы обучающегося_________________________________
недостатки работы _________________________________________________________
_______________________________________________
Сарапул, 2018 г.
Содержание
Введение………………………………………………………………….….3
1. Постановка задачи……………………………………………………..4
2. Получение автоматного алфавитного отображения информации….5
3. Построение формализованного описания работы автомата…….…..6
4. Построение кодированной таблицы переходов и выходов автомата.7
5. Определение и минимизация функций выходов автомата…………..9
6. Определение и минимизация функций переходов…………………..10
7. Преобразование в заданный базис……………………………………12
8. Введение сигналов синхронизации и установки…………………….12
9. Схема электрическая функциональная……………………………….13
Заключение……………………………………………………………………..14
Список ………………………………………………………………………….15
Введение
Теория автоматов – это раздел дискретной математики, изучающий абстрактные автоматы – вычислительные машины, представленные в виде математических моделей – и задачи, которые они могут решать [1]. Одной из задач является задача описания автомата, его реализации и формального описания в виде таблиц или графа переходов.
В текущей работе нам предстоит разобрать работу автомата Мили – конечного автомата, выходная последовательность которого зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некое значение, в вершинах записываются входящие сигналы, а дугам графа приписывают условия перехода от одного состояния в другое и входящие сигналы.
На сегодняшний день теория автоматов лежит в основе всех цифровых технологий и программного обеспечения, к примеру персональный компьютер является частным случаем практической реализации конечного автомата.
Постановка задачи
Вариант № 5
Выполнить синтез автомата МИЛИ, осуществляющего преобразование входных слов в выходные, табл.1. Базис И, ИЛИ, НЕ. RS – триггер.
| Входные слова | Выходные слова |
| а3 а2 а1 | b1 b2 |
| а2 а1 а3 а2 | b2 b1 b3 |
| а1 а3 | b3 |
| а1 а1 | b1 b2 b3 |
Табл. 1.
Получение автоматного алфавитного отображения информации
Длинна входного и выходного слова должна быть одинаковой, поэтому дополняем входные слова символом 
- справа (в конце слова), а), а выходного символом 
– слева (в начале слова), табл.2.
| Входные слова | Выходные слова |
| а3 а2 а1 | b1 b2
|
| а2 а1 а3 а2 | b2 b1 b3
|
| а1 а3 | b3
|
| а1 а1
| b1 b2 b3 |
Табл. 2.
При отображении слов одинаковые начальные отрезки входных слов должны соответствовать одинаковым начальным отрезкам выходных слов. Поэтому, для выполнения данного условия дополняем входные слова символом 
– справа (в конце слова), а выходного символом – слева (в начале слова)[2], табл.3.
| Входные слова | Выходные слова |
| а3 а2 а1 | b1 b2
|
а2 а1 а3 а2 
| b2 b1 b3
|
| а1 а3
| b3
|
| а1 а1
| b1 b2 b3
|
Табл. 3.
Построение формализованного описания работы автомата
По табл.3 строим граф и таблицу переходов – выходов. В задании необходимо синтезировать автомат Мили, т.е. каждая последняя буква входного слова должна переводить автомат в начальное состояние. При построении графа необходимо использовать минимальное число внутренних состояний автомата [3], рис.1.
Рис. 1.
Строим таблицу поведения автомата Мили, табл.4.
| Текущее состояние q(t) | Символы входного алфавита | |||
| a1 | a2 | a3 | α | |
| q0 | q3|β | q1|β | q3|β | q3|b2 |
| q1 | q2|β | q3|b1 | q3|β | q0|b3 |
| q2 | q0|b2 | --- | q1|b2 | --- |
| q3 | q0|b1 | --- | q1|β | q0b3 |
Табл. 4.