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

ВВЕДЕНИЕ

В данной работе будет выполнено проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов.
Теоретические основы канонического метода были разработаны В.М. Глушковым, сформулировавшим и доказавшим «теорему о структурной полноте».
Теорема о структурной полноте: всякая система элементарных автоматов, которая содержи автомат Мура, обладающий полной системой выходов, и какую-нибудь функционально полную систему логических элементов (элементарных автоматов без памяти), является структурно полной системой. Существует общий конструктивный приём, позволяющий свести задачу синтеза произвольных конечных автоматов к задаче структурного синтеза комбинационных схем.
На основании теоремы о структурной полноте структурная схема всякого автомата, синтезированного каноническим методом, будет состоять из двух частей: запоминающей части и комбинационной схемы. Запоминающая часть представляет собой совокупность элементарных автоматов Мура с полной системой переходов и выходов, а комбинационная часть представляет собой схему, построенную из логических элементов, составляющих функционально полный базис.
Структурный синтез автомата каноническим методом состоит из следующих этапов:
1. Кодирование состояний абстрактного автомата.
2. Кодирование абстрактных входных и выходных сигналов.
3. Составление кодированных таблиц переходов-выходов структурного автомата.
4. Формирование таблицы функций возбуждения структурного автомата.
5. Получение логических выражений функций возбуждения и выходных сигналов автомата.
6. Построение структурной схемы.
При кодировании состояний будет использован метод, называемый «кодирование случайными кодами», позволяющий упростить полученную в результате структурного синтеза схем.
 

\n
Введение…………………………………………………………………….. 4
1. Абстрактный синтез конечного автомата………………………………..5
1.1 Формирование алфавитного оператора………………………………5
1.2 Приведение оператора к автоматному виду………………………….6
1.3 Построение графа переходов абстрактного автомата……………….7
1.4 Минимизация состояний абстрактного автомата…………………..10
1.4.1 Визуальная минимизация……………………………………………10
1.4.2 Минимизация методом треугольных таблиц………………………13
1.4.3 Проверка минимизации ……………………………………………..18
2. Структурный синтез конечного автомата………………………………21
2.1 Кодирование состояний, входных и выходных
сигналов абстрактного автомата…………………………………………...21
2.2 Формирование функций возбуждения и выходных
сигналов структурного автомата…………………………………………..24
2.3 Разработка функциональной схемы структурного автомата………..30
Заключение…………………………………………………………………..36
Список используемой литературы……………………………………………….37

[1] Лупал А.М. Теория автоматов. Учебное пособие/СПбГУАП. – СПб., 2000. – 120 с., ил.
[2] Козин И.В., Иванов Н.М., Лупал А.М. Проектирование управляющих автоматов по алфавитному отображению. Учебное пособие по курсовому проектированию/ЛИАП. – Л., 1991. – 82 с., ил.
[3] Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Учебник для вузов по спец. «Электронные вычислительные машины». – 2-е изд., перераб. и доп. – Мн.: Выш. школа, 1980. – 336 с., ил.
[4] Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). – 2-е изд., перераб. и доп. – Л.: Энергия, 1979. – 232 с., ил.