padding:0cm 5.4pt 0cm 5.4pt;height:10.4pt;">
a0/-
Один из алгоритмов
минимизации полностью определенных автоматов заключается в следующем. Множество
состояний исходного абстрактного автомата разбивается на попарно пересекающиеся
классы эквивалентных состояний, далее каждый класс эквивалентности заменяется
одним состоянием. В результате получается минимальный автомат, имеющий столько
же состояний, на сколько классов эквивалентности разбиваются исходные состояния
автомата.
0 класс
эквивалентности:
|
a0, a1
|
b0
|
|
a2, a11
|
b1
|
|
a14
|
b2
|
|
a3, a4,
a10
|
b3
|
|
a5, a15
|
b4
|
|
a6
|
b5
|
|
a7, a8,
a9, a13, a16, a17, a18
|
b6
|
|
a12
|
b7
|
1
класс
эквивалентности:
|
a0
|
c0
|
|
a1
|
c1
|
|
a2
|
c2
|
|
a3
|
c3
|
|
a4
|
c4
|
|
a5, a15
|
c5
|
|
a6
|
c6
|
|
a10
|
c7
|
|
a11
|
c8
|
|
a12
|
c9
|
|
a14
|
c10
|
|
a7, a8,
a9, a13, a16, a17, a18
|
c11
|
2 класс
эквивалентности:
|
a0
|
d0
|
|
a1
|
d1
|
|
a2
|
d2
|
|
a3
|
d3
|
|
a4
|
d4
|
|
a5, a15
|
d5
|
|
a6
|
d6
|
|
a10
|
d7
|
|
a11
|
d8
|
|
a12
|
d9
|
|
a14
|
d10
|
|
a7, a8,
a9, a13, a16, a17, a18
|
d11
|
Из разбиения видно, что
классы 1 и 2 совпадают, значит, продолжать не имеет смысла.
Таблица
переходов-выходов минимизированного автомата представлена в таблице 4:
Таблица 4. Таблица
переходов-выходов минимизированного автомата
| d(t-1) |
0 |
1 |
|
d0
|
d1/1
|
d2/1
|
|
d1
|
d3/1
|
d4/1
|
|
d2
|
d7/0
|
d8/0
|
|
d3
|
- |
d5/1
|
|
d4
|
- |
d6/1
|
|
d5
|
d11/1
|
d11/0
|
|
d6
|
d11/0
|
- |
|
d7
|
- |
d9/1
|
|
d8
|
d10/0
|
d5/0
|
|
d9
|
d11/1
|
- |
|
d10
|
- |
d11/0
|
|
d11
|
d0/-
|
d0/-
|
Граф переходов
минимизированного автомата представлен в приложении 2.
2.
СТРУКТУРНЫЙ
СИНТЕЗ КОНЕЧНОГО АВТОМАТА
2.1
Кодирование состояний, входных и выходных сигналов
Для кодирования
состояний, входных и выходных сигналов конечного автомата, необходимо вычислить
число элементов памяти:
а)
рассчитаем число элементов памяти: Н = ] log2h [, где h - число
состояний после минимизации D = {
}
H = ] log2 12 [ = 4
б) рассчитаем
число входных (L) и выходных
(М) шин:
L = ] log2n[
М
=] log2m [,
где
n, m - число букв
входного и выходного алфавитов
Z = {0, 1} L = ] log2 2 [ = 1
W = {0, 1} M = ] log2 2 [ = 1
Из приведённого выше
следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим
их Q0, …, Q3.
Закодируем состояния (таблица 5) случайными кодами.
Таблица 5. Таблица кодированных состояний
| d(t-1) |
Q0
|
Q1
|
Q2
|
Q3
|
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Поможем написать работу на аналогичную тему
Получить выполненную работу или консультацию специалиста по вашему учебному
проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты:
-
Микропрограммный автомат на постоянном запоминающем устройстве для кодирования манчестерского кода
Рассмотрение назначения, строения и принципа работы простейших представителей цифровых микросхем - триггеров, регистров, мультиплексоров. Изучение структуры микропрограммного автомата на ПЗУ. Определение преимуществ применения кода Манчестер-ІІ.
-
Генератор гармонических колебаний на операционных усилителях
Генератор гармонических колебаний - устройство, без постороннего возбуждения преобразующее энергию источника питания в энергию гармонических колебаний. Проектирование элементов электрического генератора гармонических колебаний на операционном усилителе.
-
Методы расчета сложных электрических цепей
Проектирование в прикладном пакете MATLAB аналогового фильтра Баттерворта верхних частот и произвольного фильтра. Система для метода контурных токов, расчет собственных и взаимных сопротивлений контуров, токов и напряжений в методе контурных токов.
-
Микроконтроллерный регулятор температуры
Проектирование микроконтроллерного регулятора температуры, предназначенного для автоматического регулирования температуры контролируемого объекта. Состав данной системы и принцип ее работы, сфера применения. Разработка структурной и принципиальной схемы.
-
Дефокусировка. Сферическая аберрация 3 порядка. Кома и неизопланатизм
Дефокусировка, продольное смещение плоскости изображения. Сферическая аберрация, ею обладают все линзы со сферическими поверхностями. Структура пучка лучей при наличии комы. Условия апланатизма и изопланатизма. Закон синусов Аббе (условие апланатизма).
-
Методы расчета линейных электрических цепей при импульсном воздействии. Спектральный анализ сигналов
Выполнение качественного анализа переходных процессов напряжений и токов на реактивных элементах, их расчет классическим и операторным методами. Вычисление и построение графика спектральной плотности амплитуд прямоугольного импульса и искомой переменной.
-
Исследование радиопередающего устройства
Структурная схема передатчика. Электрические расчеты режимов и элементов оконечного каскада. Расчет параметров штыревой антенны. Конструкторский расчет элементов оконечной ступени. Назначение всех элементов принципиальной схемы радиопередатчика.
-
Классификация римских цифр на основе нейронных сетей
Понятие и применение нейронных сетей, особенности классификации искусственных нейронных сетей по Терехову. Решение задачи классификации римских цифр на основе нейронной сети. Составление блок-схемы алгоритма обучения нейронной сети и анализ ее качества.
-
Аперіодичний підсилювач безперервних коливань
Особливості підстлювачів з загальною базою, загальним колектором. Порівняльний аналіз каскадів підсилення. Оцінка та режими роботи схем СЕ, СБ, СК. Використання уніполярних і біполярних транзисторів, переваги. Трансформаторні та безтрансформаторні схеми.
-
Разработка арифметико-логического устройства, выполняющего операции сложения и вычитания в прямом двоичном коде
Исследование абстрактного цифрового автомата Мили заданного устройства. Алгоритм его работы, таблицы прошивки и возбуждения постоянного запоминающего устройства. Составление функции возбуждения, функциональной и электрической принципиальной схемы.
-
Астигматизм и кривизна изображения. Хроматические аберрации
Дисторсия ("искажение") абсолютная и относительная. Хроматические аберрации, проявление зависимости характеристик оптической системы от длины волны света. Принципы ахроматизации оптических систем. Абсолютный и относительный хроматизм увеличения.
-
Математические основы теории систем
Математическая модель объекта управления в пространстве состояния. Структурная схема и сигнальный граф. Формула Мейсона и передаточная функция объекта управления. Матричное уравнение для выходной переменной. Условия устойчивости системы и ее корни.
-
Проектирование и синтез дискретных устройств
Синтез дискретного устройства, его структурная схема. Расчет дешифратора и индикаторов, их проектирование. Карты Карно. Синтез счетной схемы. Делитель частоты. Проектирование конечного автомата и его описание. Анализ сигналов и минимизация автомата.
-
Синтез цифрового автомата
Расчет схемы цифрового автомата, функционирующего в соответствии с заданным алгоритмом. Кодирование состояний. Составление таблицы функционирования комбинационного узла автомата. Запись логических выражений. Описание выбранного дешифратора и триггера.
-
Анализ передачи периодических сигналов через линейные электрические цепи
Определение характера и уровня изменения сигнала амплитудно-частотного и фазо-частотного спектра. Построение графиков, расчет комплексного коэффициента передачи цепи. Особенности определения напряжения на выходе при воздействии на входе заданного сигнала.
-
Разработка функциональной схемы конечного автомата
Алгоритм работы автомата Мили в табличном виде. Графический способ задания автомата. Синтез автомата Мили на Т-триггерах. Кодирование состояний автомата. Таблицы кодирования входных и выходных сигналов. Таблица переходов и выходов абстрактного автомата.
-
Разработка функциональной и принципиальной схем управляющего автомата
Разработка функциональной и принципиальной схем управляющего устройства в виде цифрового автомата. Синтез синхронного счётчика. Минимизация функций входов для триггеров с помощью карт Карно. Синтез дешифратора и тактового генератора, функции выхода.
-
Анализ системы управления
Динамические свойства объекта управления. Динамические свойства последовательного соединения исполнительного механизма и объекта управления. Разработка релейного регулятора, перевод объекта из начального состояния в конечное. Выбор структуры и параметров.
-
Абстрактные цифровые автоматы
Основные понятия абстрактных цифровых автоматов, их классификация и способы задания. Связь между моделями Мили и Мура. Эквивалентные автоматы и эквивалентные их преобразования. Минимизация числа внутренних состояний автомата, алгоритм Ауфенкампа-Хона.
-
Последовательностные функциональные узлы
Схема строения цифровых автоматов, применяемых в цифровой технике. Отличия синхронных и асинхронных последовательностных устройств. Логические уравнения для определения работы автомата Мура. Синхронные триггеры и синтез последовательностного устройства.
|