Добавлен: 05.12.2023
Просмотров: 412
Скачиваний: 18
| 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/- |
={(????5,????2) = ????8.
Получается следующий автомат Мура рис. 1:
Рисунок 1 – полученный автомат МУРА
Проверим все переходы в автомате Мура:
???? ????2 ????2 ????1 ????1 ????2 ????2 ????1 ????2 ????1 ????1 ????2 ????1 ????1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
????1 → ???? 2 → ????2 → ????3 → ????3 → ???? 7 → ???? 4 → ????3 → ????7 → ???? 5 → ???? 6 → ????5 → ???? 6 ???? ????2 ????2 ????1 ????1 ????1 ????2 ????1 ????1 ????2 ????2 ????2 ????2
????1 ????1 ????1 ????2 ????2 ????1 ????2 ????1
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
→ ???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? .
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
????2 ????2 ????2 ????2 ????2 ????1 ????2 ????1 ????1
Проверим исходный автомат на том же входном слове:
???? ????2 ????2 ????1 ????1 ????2 ????2 ????1 ????2 ????1 ????1 ????2 ????1 ????1
???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? → ???? → ????
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
???? ????2 ????2 ????1 ????1 ????1 ????2 ????1 ????1 ????2 ????2 ????2 ????2 ????2 ????1 ????1 ????1 ????2 ????2 ????1 ????2 ????1
→ ???? 5 → ???? 3 → ???? 4 → ???? 5 → ???? 2 → ???? 5 → ???? 3 → ????1 →
????2. ????2 ????2 ????2 ????2 ????1 ????2 ????1 ????1Выходные словасовпадают, значитавтоматыэквивалентны.1.1.2 Преобразование автомата Мура в автомат МилиПеренесём выходные сигналы из состояний на входящие дуги.Проверим все переходы в автомате Мили:????????2 ????2 ????1 ????1 ????2 ????2 ????1 ????2 ????1 ????1 ????2 ????1 ????1???? →???? →???? →???? →???? →???? →???? →???? →???? →???? →???? →???? →????↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓????????2 ????2 ????1 ????1 ????1 ????2 ????1 ????1 ????2 ????2 ????2 ????2 ????2 ????1 ????1 ????1 ????2 ????2 ????1 ????2 ????1→????8→????5→????6→????8→????4→????7→????5→????1→????3. ????2 ????2 ????2 ????2 ????1 ????2 ????1 ????1Выходное слово опять совпадаетсвыходным словомисходногоавтомата,а следовательно автоматыэквивалентны.Выводы: Эквивалентные автоматы одного типа могут иметь разное количество состояний.ЗАКЛЮЧЕНИЕВ процессе выполнения работы мной были закреплены знания о синтезе конечных автоматов и получена практика в построении комбинационных схем.В данной работе мной было выполнено проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов. Построены граф переходов абстрактного автомата с 17 состояниями и таблицы переходов-выходов. Минимизация состояний автомата выполнена путем разбиения на группы эквивалентных между собой состояний. После чего был построен минимальный граф Мили с 11 состояниями. Выполнен синтез абстрактного автомата Мура по алгоритму в соответствии с вариантом и переведен автомат Мура в автомат Мили.
СПИСОК ЛИТЕРАТУРЫ
-
Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). – 2-е изд., перераб. и доп. – Л.: Энергия, 1979. – 232 с., ил. -
Дегтярев В.М., Ерош И.Л., Михайлов В.В. Проектирование цифровых автоматов.-Л.:ЛИАП, 1974г. -
Козин И.В., Иванов Н.М., Лупал А.М. Проектирование управляющих автоматов по алфавитному отображению. Учебное пособие по курсовому проектированию/ЛИАП. – Л., 1991. – 82 с., ил. -
Лупал А.М. Теория автоматов. Учебное пособие/СПбГУАП. – СПб., 2000. – 120 с., ил. -
Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Учебник для вузов по спец. «Электронные вычислительные машины». – 2-е изд., перераб. и доп. – Мн.: Выш. школа, 1980. – 336 с., ил. -
Конспект лекций по дисциплине «Теория автоматов», преподаватель Глебов Е.А., 2005-2006 уч.г.