Основы теории выбора средств реализации информационно-вычислительных систем. Практическая работа по дисциплине Основы теории выбора средств реализации информационновычислительных систем по теме Разработка цифрового автомата
![]()
|
М ![]() Федеральное государственное бюджетное образовательное учреждение высшего образования «Пензенский государственный технологический университет» (ПензГТУ) Кафедра «Вычислительные машины и системы» Практическая работа по дисциплине «Основы теории выбора средств реализации информационно-вычислительных систем» по теме «Разработка цифрового автомата» Вариант №21 Выполнил: студент группы 19ИВ1бзи Семенов Е.П. Проверил: Доцент каф. “ВМиС”, к.т.н. Мартышкин А.И. Пенза 2020Задание №11. По заданной совмещенной таблице переходов и выходов автомата Мили построить: прямую таблицу переходов; обратную таблицу переходов; граф; записать СКУ и СВФ. Вариант 21
Решение. Составим прямую таблицу переходов автомата Мили (табл. 1.1), в которой последовательно перечислим все переходы сначала из первого состояния, затем из второго и т.д. Таблица 1.1. Прямая таблица переходов автомата Мили
Составим обратную таблицу переходов автомата Мили (табл. 1.2), в которой сначала запишем все переходы в первое состояние, затем во второе и т.д. Таблица 1.2. Обратная таблица переходов автомата Мили
Построим граф автомата Мили (рис. 1.1), вершины которого соответствуют состояниям, а дуги – переходам между ними. В начале каждой дуги запишем входной сигнал zfZ, вызывающий переход: as= (am, zf), а в конце дуги – выходной сигнал wgW, формируемый на переходе. ![]() Рис. 1.1. Граф автомата Мили Составим СКУ и СВФ, которые определяют функции переходов и выходов автомата соответственно. Система канонических уравнений (СКУ): ![]() Система выходных функций (СВФ): ![]() 2. Преобразовать заданный в п.1 автомат Мили в эквивалентный ему автомат Мура. Для полученного автомата Мура построить: отмеченную таблицу переходов; прямую таблицу переходов; обратную таблицу переходов; граф; СКУ и СВФ; Решение. Для автомата Мура: Z / = Z = {z1, z2}; W / = W = {w1, w2, w3, w4, w5}. Построим множество А/. Для этого найдем множество пар, порождаемых каждым состоянием автомата Мили S. Каждую пару обозначим символами b1, b2, ...: A1 = {(a1, w2), (a1, w4)} = {b1, b2}; A2 = {(a2, w3)} = {b3}; A3 = {(a3, w5)} = {b4}; A4 = {(a4, w1), (a4, w5)} = {b5, b6}. A /={b1, b2, b3, b4, b5, b6}. Для определения функции / с каждым состоянием вида (as, wg), представляющим собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары: /(b1) = w2; /(b2) = w4; /(b3) = w3; /(b4) = /(b6) = w5; /(b5) = w1. Для полученного автомата Мура построим отмеченную таблицу переходов (табл. 1.3). Таблица 1.3. Отмеченная таблица переходов S /
Составим прямую таблицу переходов автомата Мура (табл. 1.4), в которой последовательно перечислим все переходы сначала из первого состояния, затем из второго и т.д. Таблица 1.4. Прямая таблица переходов автомата Мура
Составим обратную таблицу переходов автомата Мура (табл. 1.5), в которой сначала запишем все переходы в первое состояние, затем во второе и т.д. Таблица 1.5. Обратная таблица переходов автомата Мура
Построим граф автомата Мура (рис. 1.2), вершины которого соответствуют состояниям, а дуги – переходам между ними. В начале каждой дуги запишем входной сигнал zfZ, вызывающий переход: as= (am, zf), а выходной сигнал wgW укажем рядом с вершиной, отмеченной состоянием am, в котором он формируется. ![]() Рис. 1.2. Граф автомата Мура Составим СКУ и СВФ, которые определяют функции переходов и выходов автомата соответственно. Система канонических уравнений (СКУ): ![]() Система выходных функций (СВФ): ![]() 3. Преобразовать полученный в п.2 автомат Мура в эквивалентный ему автомат Мили и выполнить его минимизацию. Решение. Для автомата Мили: Z / = Z = {z1, z2}; W / = W = {w1w2, w3, w4, w5}; B / =B = {b1, b2, b3, b4, b5, b6}; /= ;b1/ = b1. На рис. 1.3 приведен граф автомата Мура S, эквивалентного автомату Мили S/. Для преобразования выходной сигнал (wg), записанный рядом с вершиной (bs), переносим на все дуги, входящие в эту вершину. ![]() ![]() Рис. 1.3. Автомата Мили S/, эквивалентный автомату МураS Табл. 1.6 − совмещенная таблица переходов и выходов автомата Мили. Для её получения вместе с состояниями перехода as запишем отмечающие их выходные сигналы wg.
Выполним минимизацию полученного автомата Мили с помощью треугольной таблицы. По табл. 1.6 составляется треугольная таблица (табл. 1.7), столбцы и строки которой сопоставляются с состояниями автомата. Для упрощения записи в этой таблице вместо bi будем писать i. В треугольной таблице на пересечении строки mи столбца s поставим: X (крест), если состояния bm и bs имеют разные выходные сигналы; множество всех пар состояний, следующих за парой (bm, bs) и отличных от неё, эквивалентность которых необходима для эквивалентности пары (bm, bs). V (птичка), если за парой (bm,bs), не следуют пары, отличные от (bm, bs). Таблица 1.7. Треугольная таблица для автомата S
В результате получим эквивалентные пары состояний: 12, 56. Выполним замену состояний bi ≡ ci, при этом учтем, что каждый класс эквивалентности {b1, b2} и {b5, b6} можно заменить одним состоянием: {b1, b2} = c1, b3 = c2, b4 = c3, {b5, b6} = c4. Построим совмещенную таблицу переходов и выходов минимального автомата Мили (табл. 1.8). Таблица 1.8. Совмещенная таблица переходов и выходов минимального автомата Мили
|