Теория автоматов

  • 09 марта 2014 г.
  • 4225 Слова
Задание
В ходе курсовой работы требуется:
– составить по заданному графу абстрактного автомата таблицу переходов, таблицу выходов;
– минимизировать число состояний абстрактного автомата;
– построить граф минимизированного автомата (автомата Мура), изображенного на рисунке 1;
– разработать каноническим методом структурную схему минимизированного автомата;
–произвести структурный синтез автомата на элементах памяти для триггеров (RS-триггерах);
– на вход подается последовательность из цифр входящих в индивидуальный шифр(5336).


[pic]

Рисунок 1.1 – Граф абстрактного автомата Мура


Реферат
УДК 621.436


Курсовой проект содержит 27 страницы, 14 рисунков, 27 таблиц.
Конечный автомат, граф, таблица переходов, таблица выходов,минимизация, состояние, канонический метод, структурный синтез, элемент памяти, триггер, автомат Мили.
Цель работы – минимизировать абстрактный автомат, составить функциональную схему.
В процессе работы было минимизировано число состояний абстрактного автомата, построен минимизированный граф, произведен структурный синтез данного автомата.
Курсовая работа выполнена в текстовом редактореMicrosoft Word 2003, моделирование схемы произведено в Electronics Workbench, функциональная схема спроектирована в AutoCAD 2006.
Содержание
Введение 5
1 Абстрактные автоматы 6
1.1 Реализация конечного автомата 6
1.2 Постановка и решение задач синтеза автоматов 6
1.3 Удовлетворение условий корректности построения структурных схем 8
1.4 Определение абстрактного автомата с наименьшим числомсостояний 8
2 Минимизация конечного автомата 9
2.1 Этапы минимизации абстрактных автоматов 9
2.2 Классы совместимости автоматов 9
3 Этапы синтеза структурного автомата 10
3.1 Кодирование состояний абстрактных автоматов 10
3.2 Составление кодированных таблиц переходов выходов структурного автомата 10
4 Элементарная база цифровых автоматов 10
5 Триггеры 11
5.1 Классификация триггеров 11
5.2RS-триггер 12
5.3 JK-триггер 13
5.4 D-триггер 14
5.5 T-триггер 14
6 Расчетная часть 16
6.1 Первый и второй этапы минимизации абстрактного автомата 16
6.2 Третий этап минимизации абстрактного автомата 18
6.3 Синтез структурного автомата 21
6.4 Получение логических выражений функций возбуждения и выходных сигналов 23
6.5 Моделирование схемы в Electronics Workbench 25
Заключение 28Библиографический список 29
Введение
Конечный автомат является простейшей моделью вычислительного устройства. Хотя теория конечных автоматов изучает очень простые модели, она является фундаментом большого числа разнообразных приложений. Эти приложения — от языковых процессоров до систем управления реального времени и протоколов связи — покрывают значительную долю систем, разработкой, реализацией и анализом которыхзанимается информатика.
Существуют более сложные, не функциональные преобразователи информации; их реакция зависит не только от входа в данный момент, но и от того, что было на входе раньше, от входной истории. Такие преобразователи называются автоматами. Число возможных входных историй бесконечно, даже если различных элементов входной информации у автомата конечное число (как в конечномфункциональном преобразователе). Если автомат по-разному будет себя вести для каждой возможной предыстории, то такой «бесконечный» автомат должен иметь бесконечный ресурс — память, чтобы все эти предыстории как-то запоминать.
Случай, когда количество классов эквивалентных входных историй конечно, является простейшим, и именно он вызвал значительный интерес и имеет очень широкие применения. Соответствующая формальнаямодель называется конечным автоматным преобразователем информации, или просто конечным автоматом. Внутренним состоянием автомата назовем класс эквивалентности его входных историй.
На один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в данный момент....
tracking img