Добавлен: 05.12.2023
Просмотров: 185
Скачиваний: 13
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Из разбиения видно, что классы 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. ПРАКТИЧЕСКАЯ ЧАСТЬ
1.1.1 Преобразование автомата Мили в автомат Мура
Разделим состояния автомата Мили в соответствии с выходными сигналами:
????1: ????1 = {(????1,????2) = ????2,????2:????2 = {(????2,????2) = ????4,????3: ????3 = {(????3,????2) = ????5,
????4:????4 = {(????4,????2) = ????6,????5: ????5
={(????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 уч.г.