Синтез конечных автоматов Мура

 

5.2.1. Абстрактный синтез автомата Мура

Для синтеза схемы конечного автомата Мура необходимо иметь таблицу соответствия, которая получается на основе словесной формулировки работы синтезируемого автомата.

Пример 5.. Получена следующая таблица соответствия: U ₀ U ₁ U ₂ U ₀ U ₁ U ₂ U ₃ U ₀ – V ₀ V ₁ V ₂ V ₀ V ₂ V ₁ V ₁ V ₀. Аналогично, как и при синтезе автомата Мили, каждому переходу таблицы соответствия присваивается внутреннее состояние и получается таблица 5.21.

Таблица 5.21.

Таблица соответствия

U 0	–	а 0	–	V 0
U 1	–	а 1	–	V 1
U 2	–	а 2	–	V 2
U 0	–	а 3	–	V 0
U 1	–	а 4	–	V 2
U 2	–	а 5	–	V 1
U 3	–	а 6	–	V 1
U 0	–	а 7	–	V 0

 

Для синтеза схемы автомата Мура строится отмеченная таблица переходов. Отмеченная таблица переходов отличается от совмещенной таблицы переходов и выходов автомата Мили тем, что выходами автомата отмечаются все столбцы таблицы переходов. В клетках этой таблицы ставятся только внутренние состояния автомата, число строк и столбцов будет таким же, как и в совмещенной таблице переходов и выходов автомата Мили.

Таблица 5.22.

Отмеченная таблица переходов

	V 0	V 1	V 2	V 0	V 2	V 1	V 1	V 0
	а 0	а 1	а 2	а 3	а 4	а 5	а 6	а 7
U 0	а 0		а 3	а 3			а 7	а 7
U 1	а 1	а 1		а 4	а 4
U 2		а 2	а 2		а 5	а 5
U 3						а 6	а 6

 

Для минимизации отмеченной таблицы переходов (для объединения столбцов) существуют два условия:

- необходимое условие заключается в том, что внутренние состояния, которыми обозначены столбцы, могут объединяться между собой, если они отмечены одинаковыми выходами;

- достаточное условие позволяет объединять столбцы только в том случае, если после переобозначения внутренних состояний в объединяемых клетках будут находиться одинаковые внутренние состояния, или одна клетка заполнена, а другая пустая, или обе клетки пустые.

При минимизации отмеченной таблицы переходов все символы внутренних состояний развиваются на R группы, количество которых равно числу попарно различимых выходных символов. В каждую группу вносятся только те символы внутренних состояний а_i, которые отмечены одинаковыми выходными символами V_j. В отмеченной таблице переходов 5.22 . Переобозначив внутренние состояния символом g по необходимому условию получаем

х ₀ – а ₀ а ₃ а ₇, отмеченные выходом V ₀

х ₁ – а ₁ а ₅ а ₆, отмеченные выходом V ₁

х ₂ – а ₂ а ₄, отмеченные выходом V ₂

После переобозначения внутренних состояний строится таблица 5.23 для проверки выполнения достаточного условия.

Таблица 5.23.

Отмеченная таблица переходов

	V 0	V 1	V 2	V 0	V 2	V 1	V 1	V 0
	а 0	а 1	а 2	а 3	а 4	а 5	а 6	а 7
	g 0	g 1	g 2	g 0	g 2	g 1	g 1	g 0
U 0	g 0		g 0	g 0			g 0	g 0
U 1	g 1	g 1		g 2	g 2
U 2		g 2	g 2		g 1	g 1
U 3						g 1	g 1

 

В полученной таблице 5.23 проверяется выполнение достаточного условия. В строке U ₁ ранее намеченные к объединению столбцы а ₀ и а ₃ по достаточному условию не объединяются в клетке столбца а ₀ и строки U ₁ стоит внутреннее состояние х ₁, а клетке строки U ₁ и столбца а ₃ внутреннее состояние х ₂.

По аналогичным причинам не объединяются столбцы а ₁ а ₅ и а ₂ а ₄, поэтому необходимо произвести новое переобозначение внутренних состояний

g ₀ – а ₀ а ₇

g ₁ – а ₁

g ₂ – а ₅ а ₆

g ₃ – а ₂

g ₄ – а ₄

g ₅ – а ₃

Для проверки выполнения достаточного условия строится таблица 5.24. Из таблицы 5.24 следует, что достаточные условия выполняются. Минимальная таблица переходов автомата Мура представлена таблицей 5.25.

Таблица 5.24.

Отмеченная таблица переходов

	V 0	V 1	V 2	V 0	V 2	V 1	V 1	V 0
	а 0	а 1	а 2	а 3	а 4	а 5	а 6	а 7
	g 0	g 1	g 3	g 5	g 4	g 2	g 2	g 0
U 0	g 0		g 5	g 5			g 0	g 0
U 1	g 1	g 1		g 4	g 4
U 2		g 3	g 3		g 2	g 2
U 3						g 2	g 2

 

Таблица 5.25.

Минимальная таблица автомата Мура

	V 0	V 1	V 2	V 0	V 2	V 1
	g 0	g 1	g 3	g 5	g 4	g 2
U 0	g 0		g 5	g 5		g 0
U 1	g 1	g 1		g 4	g 4
U 2		g 3	g 3		g 2	g 2
U 3						g 2

 

 

5.2.2. Структурный синтез автоматов Мура

Кодирование входов, выходов и внутренних состояний осуществляется так же, как и для автоматов Мили

Для кодирования внутренних состояний необходимо построить граф автомата (рис. 5.9).

 

 

 

Рис. 5.9. Граф автомата Мура

 

После кодирования входов, выходов и внутренних состояний строится структурная таблица переходов автомата Мура.

Таблица 5.26.

Структурная таблица переходов

	у 1 у 2
Q 1 Q 2 Q 3 х 1 х 2

 

Из структурной таблицы 5.26 следует, что синтезируемый автомат Мура имеет два входа х ₁ х ₂, два выхода у ₁ у ₂ и три элемента памяти Q ₁ Q ₂ Q ₃.

Уравнения выходов получаются непосредственно из структурной таблицы переходов следующим образом. Из столбцов где у ₁ равен единице в уравнение у ₁ в качестве слагаемых берутся коды внутренних состояний, которыми обозначены столбцы таблицы переходов. Аналогично записывается уравнение для у ₂

.

Как видно из уравнений выходы у ₁ у ₂ автомата Мура формируются только элементами памяти, а выходы автомата Мили формируются как элементами памяти, так и входами х ₁ х …

Для получения уравнений возбуждения элементов памяти необходимо выбрать элементы автоматики и телемеханики, которые будут использоваться в качестве элементов памяти в автомате Мура.

Если в качестве элементов памяти будет использоваться реле, то таблица переходов автомата Мура 5.26 одновременно будет и таблицей возбуждения.

Для получения минимальных уравнений возбуждения элементов памяти необходимо таблицу 5.26 преобразовать к виду таблицы минимизации на пять переменных. Для этого надо последние две строки поменять местами и добавить два столбца с недостающими кодами 010 и 101.

Таблица 5.27.

Преобразовательная таблица переходов

q 1 q 2 q 3 х 1 х 2

 

Получение уравнения возбуждения элемента памяти Q ₁

Таблица 5.28.

Таблица минимизации

			011

 

 

.

Аналогично получаются уравнения возбуждения элементов памяти Q ₂ и Q ₃.

Таблица 5.29.

	000

 

 

.

Таблица 5.30.

 

 

.

Схема электрическая функциональная автомата Мура на релейно-контактных элементах показана на рисунке 5.1.

 

 

Рис. 5.10. Схема электрическая функциональная автомата Мура