Абстрактная и структурная теории конечных автоматов. Структура операционного устройства. Способы задания автоматов

УДК 681.3                                       

Теория автоматов / Е.И.Зайцев. –М.: МГАПИ, 2002. –59 с.

ISBN 5-8068-0252-3

Рекомендовано Ученым Советом МГАПИ в качестве учебного пособия для специальности 2201.

Рецензент:  к.т.н., доцент

Предлагаемое издание рекомендуется в качестве учебного пособия  для студентов, обучающихся по специальности 2201 «Вычислительные машины, комплексы, системы и сети». 

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

ISBN 5-8068-0252-3

  1402010000                                                  ã Зайцев Е.И., 2002      ^{ЛР020418-97}

СОДЕРЖАНИЕ

ВВЕДЕНИЕ  ………………………………………………………………   4

1.  ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АВТОМАТОВ …………………..    5

1.1. Определение конечного автомата. Автоматы Мили и Мура ………   5

1.2. Способы задания автоматов ………………………………………….   8

1.3. Минимизация абстрактных таблиц переходов и выходов автомата …………………………………………………………………...  15

2.  ФУНКЦИОНАЛЬНО-ЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕ ОПЕРАЦИОННЫХ УСТРОЙСТВ  …………………………………….  19

2.1.  Структура операционного устройства ……………………………..  19

2.2.  Разработка операционного автомата . ……………………………...  21

2.3.  Представление чисел в разрядной сетке автомата  ………………..  30

3.  СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ …………………  33

3.1.  Способ получения абстрактных таблиц переходов и выходов автомата по графу алгоритма   ...……………………………  33

3.2.  Канонический метод структурного синтеза ……………………….  38

3.3.  Противогоночное кодирование состояний автомата ……………… 40

3.4.  Метод получения функций возбуждения и выходов автомата  ….  46

3.5.  Синтез комбинационных схем в потенциальной системе элементов ………………………………………………………..  48

4.  МЕТОДИКА ВЫПОЛНЕНИЯ КУРСОВОГО ПРОЕКТА  …………… 55

4.1.  Основные этапы курсового проекта  ……………………………….. 55

4.2.  Содержание разделов пояснительной записки  ……………………. 56

СПИСОК ЛИТЕРАТУРЫ  ………………..………………….…………... 59

ВВЕДЕНИЕ

Для формального описания электронных схем, которые делят на два типа в зависимости от того, каким образом выходной сигнал зависит от входного, используют соответствующий аппарат. Математический аппарат алгебры логики пригоден для анализа и синтеза схем без памяти, то есть таких схем, в которых совокупность выходных сигналов в любой момент времени представляет собой однозначную функцию входных сигналов в тот же момент времени. Реализуемый в этих схемах способ обработки информации называется комбинационным, так как результат на выходе зависит только от комбинации входных сигналов. Схемы с памятью, алгоритм работы которых зависит от времени, описываются с помощью математического аппарата теории конечных автоматов. Понятие цифрового автомата, как средства для представления и обработки любых видов информации, является одним из основных в информатике. Конечными автоматами являются как отдельные узлы ЭВМ, так и вся вычислительная машина.

С появлением новых инструментальных средств и подходов в области программного обеспечения модель конечного автомата широко используется не только для описания функционирования устройств переработки дискретной информации, но и для описания поведения программных агентов, то есть положена в основу технической имитации интеллекта. Автомат в этом случае рассматривают как эквивалент  некоторой абстрактной среды, переходящей из одного состояния в другое в результате целенаправленных действий когнитивных агентов. Использование аппарата теории автоматов для анализа и проектирования многоагентных систем, в первую очередь, связано с объектно-ориентированным подходом, который является в настоящее время одним из наиболее интенсивно развивающихся направлений теоретического и прикладного программирования.

1.  ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АВТОМАТОВ

1.1. Определение конечного автомата. Автоматы Мили и Мура

Абстрактный автомат (рис.1.1) задаётся как совокупность шести объектов:

·  конечного множества Z={z₁,z₂ ... z_N} входных сигналов  (входной алфавит);

·  конечного множества W={w₁,w_2,...w_G} выходных сигналов (выходной алфавит);

·  произвольного множества  A={a₁,a₂...a_M} состояний автомата  (алфавит внутренних состояний);

·  элемента a₀  из множества  A, называемого начальным состоянием автомата;

·  функцией d(a,z) переходов автомата;

·  функцией l(a,z) выходов автомата.

Рис.1.1  Абстрактный автомат

Абстрактный автомат  реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Автомат называется конечным, если его входной алфавит и множество его внутренних состояний – конечные множества. Чтобы задать конечный автомат, необходимо описать входной и выходной алфавиты, алфавит состояний, а также функции переходов и выходов.