 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Четвёртый этап минимизации
В некоторых случаях после получения отмеченной таблицы переходов автомата возможен четвертый этап минимизации. Правда этот этап не всегда приводит к уменьшению числа состояний и часто является проверочным. Алгоритм этого этапа рассмотрим на примере.
Пусть есть автомат, заданный следующей отмеченной таблицей переходов:
| yg | y 1 | y 1 | y 1 | y 2 | y 1 | y 2 | y 2 | y 2 |
| xj / ai | ||||||||
| x 1 | ||||||||
| x 2 | ||||||||
| х 3 |
Алгоритм минимизации заключается в следующем:
1. Все внутренние состояния разбиваются на группы по числу выходных сигналов. В нашем случае есть два выходных сигнала y 1 и y 2 и, следовательно, будет две группы, которые мы обозначим буквами a и b.
2.
| 3 5 6 7 aba aba bab aba |
| b |
| 0 1 2 4 aba bab aba aba |
| a |
По таблице переходов автомата определяют, к каким группам принадлежат внутренние состояния, в которые автомат переходит из данного состояния под воздействием каждой буквы входного алфавита. Эти состояния запишем в виде последовательности букв под каждым из состояний автомата. Например, из состояния 0 автомат переходит в состояния 2, 3 и 1, которые принадлежат соответственно к следующим группам a, b и a. Эта последовательность букв (aba) и записывается под состоянием 0:
3.
| 3 5 7 acb acb acb |
| c |
| cbd |
| d |
Проводят новое разделение внутренних состояний на группы, объединяя в каждой группе состояния, отмеченные одинаковой последовательностью букв. В нашем случае каждая из двух групп распадается на две группы, по числу различных последовательностей букв:
| 0 2 4 acb acb acb |
| a |
| cbd |
| b |
4. Пользуясь таблицей переходов автомата, вновь отмечают каждое состояние последовательностью букв. Разделение состояний на новые группы продолжают до тех пор, пока новые группы состояний появляться не будут. В нашем случае минимизация заканчивается на втором шаге, так как все состояния, входящие в группы а и с, отмечены одинаковыми последовательностями букв, а группа b и d содержат только по одному состоянию.
Все состояния, входящие в каждую из этих групп, можно заменить одним состоянием той же группы. Взяв в качестве представителей групп состояния 0, 1, 3 и 6 и обозначив их символами a 0, a 1, a 2 и a 3 соответственно, получим следующую таблицу переходов с минимальным числом внутренних состояний.
| yg | y 1 | y 1 | y 2 | y 2 |
| xj /ai | a 0 | a 1 | a 2 | a 3 |
| x 1 | a 0 | a 2 | a 0 | a 2 |
| x 2 | a 2 | a 1 | a 2 | a 1 |
| x 3 | a 1 | a 3 | a 1 | a 3 |
Для построения автомата Мили воспользуемся рассмотренным ранее алгоритмом, для чего в каждую клетку совмещенной таблицы переходов и выходов запишем значения выходного сигнала, которым отмечено, находящееся здесь состояние.
| xj /ai | a 0 | a 1 | a 2 | a 3 |
| x 1 | a 0/ y 1 | a 2/ y 2 | a 0/y1 | a 2/ y 2 |
| x 2 | a 2/ y 2 | a 1/ y 1 | a 2/y2 | a 1/ y 1 |
| x 3 | a 1/ y 1 | a 3/ y 2 | a 1/y1 | a 3/ y 2 |
В полученной таблице колонки, помеченные состояниями a 0 и a 2, a 1 и a 3 идентичны, что позволяет при минимизации исключить состояния a 2 и a 3. В результате получаем таблицу переходов и выходов автомата Мили, имеющего два состояния a 0 и a 1.
| xj / ai | a 0 | a 1 |
| x 1 | a 0/ y 1 | a 0/ y 2 |
| x 2 | a 0/ y 2 | a 1/ y 1 |
| x 3 | a 1/ y 1 | a 1/ y 2 |
Вопросы к лекции 14:
1. Первый этап минимизации внутренних состояний автомата?
2. Второй этап минимизации внутренних состояний автомата?
3. Третий этап минимизации внутренних состояний автомата?
4. Четвертый этап минимизации внутренних состояний автомата?
5. Рассказать кратко об алгоритме минимизации?
6. В чем заключается смысл минимизации?
7. Надо ли при минимизации исключать такие состояния, в которые автомат из нулевого состояния никогда перейти не может?
8. Приводит ли четвертый этап минимизации к уменьшению числа состояний?
ЛЕКЦИЯ 15
Поиск по сайту: