- •Раздел V. Основы теории конечных автоматов
- •1. Основные понятия теории
- •1.1. Автоматы Мили. Граф переходов. Однотактные и многотактные автоматы
- •1.2. Таблица состояний автомата
- •1.3. Реакция, эквивалентность и сокращение автоматов
- •1.4. Свойства классов k - эквивалентности автоматов. Построение сокращенных автоматов
- •1.5. Автоматы Мура
- •5) G : х q q - функция переходов.
- •2.1. Числовая форма задания автоматов. Двоичные автоматы
- •2. Анализ и синтез двоичных автоматов
- •2.2. Канонические уравнения и схема автомата
- •1. Канонические уравнения.
- •2.Схема автомата.
- •2.3. Оптимальные автоматы
- •2. По заданной канонической таблице состояний построить оптимальную функциональную схему автомата и граф пере-ходов.
1.2. Таблица состояний автомата
Рассмотрим наряду с графом переходов табличный способ задания автоматов. Обозначим текущий момент вре-мени через ti , а предыдущий момент времени через ti-1.
Определение. Таблица, задающая функции выходов F и переходов G автомата Мили в виде таблиц, называется таблицей состояний автомата. Входными переменными таблицы являются множества Q, Х , описывающие вход и
284
внутреннее состояние автомата, причем вход задается в те-кущий момент времени ti , а внутреннее состояние – в пре-дыдущий момент времени ti-1. Выходными данными табли-цы являются значения Q, Z в текущий момент времени ti . Для инициального автомата начальные состояния указы-ваются отдельно.
Пример . Построить таблицу состояний для автомата, рассмотренного в Примере п. 1.1.
Решение. 1. Входные столбцы таблицы получим, упорядо-чивая сочетания (Xi, Qj) ((X1 - X6), (Qож , Qв/A, Qв/В )) в лекси-кографическом порядке. В выходных столбцах будут нахо-диться соответствующие им значения Z(Xi, Qj), Q(Xi, Qj), которые переносим из графа переходов.
-
X
Qj (ti-1)
Z
Qj (ti)
X1
Qож
Z1
Qож
X1
Qв/A
Z1
Qож
X1
Qв/В
Z1
Qож
X2
Qож
Z1
Qв/A
X2
Qв/A
Z1
Qв/A
X2
Qв/В
Z1
Qв/A
X3
Qож
Z1
Qв/В
X3
Qв/A
Z1
Qв/В
X3
Qв/В
Z1
Qв/В
X4
Qож
Z4
Qож
X4
Qв/A
Z2
Qв/A
X4
Qв/В
Z4
Qв/В
X5
Qож
Z4
Qож
X5
Qв/A
Z4
Qв/A
X5
Qв/В
Z3
Qв/В
X6
Qож
Z4
Qож
X6
Qв/A
Z4
Qв/A
X6
Qв/В
Z4
Qв/В
285
Замечание. В случае применения числовых кодировок входов, выходов и внутренних состояний автоматов в дво-ичной или многозначной системе счисления таблица со-стояний будет, соответственно, таблицей истинности неко-
торых функций в алгебре логики либо многозначной логи-ке. Данные функции, как правило, являются частично определенными.
Задачи.
1. Построить таблицы состояний для автоматов, указанных в Задачах 1-6 п.1.1.