Математический аппарат инженера - страница 48
Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s(ν + 1) и у(ν) представлены двоичными кодами:
Рис. 239. Структурная схема конечного автомата
Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x>1(ν), х>2(ν) и переменным состояния s(ν), s>2(ν), а также три выхода, соответствующие переменным состояния s>1(ν + 1), s>2(ν + 1) и выходной переменной у>1(ν). Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки З>1 и З>2, получим структурную схему автомата (рис. 239).
7. Минимизация автоматов. С утилитарной точки зрения интерес представляет только зависимость между входами и выходами автомата, а роль его состоянии сводится исключительно к участию в формировании этих зависимостей в качестве промежуточных переменных. Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состоянии автомата. В то же
- 572 -
время этот выбор естественно подчинить определенным целям, например, минимизации числа состояний или оптимизации автомата в каком-либо смысле. Следует иметь в виду, что с уменьшением числа состоянии уменьшается и количество требуемых элементов памяти, но это может привести к усложнению комбинационной схемы автомата. Поэтому синтез наиболее экономичного автомата часто требует поиска удачного компромисса между сложностью его комбинационной и запоминающих частей.
Рис. 240. Граф конечного автомата (а) и его сокращенная форма (б)
Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы М>1 и М>2, находящиеся соответственно в начальных состояниях, σ>i и σ>j (обозначения М>1 и М>2 могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М>1 и М>2 в данных состояниях σ>i и σ>j неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:
1) состояния σ>i и σ>j автомата явно различимы, если различаются соответствующие, им строки в таблице выходов;
2) состояния σ>i и σ>j автомата явно эквививалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера σ>i на номер σ>j (или наоборот).
Например, для автомата, граф которого изображен на рис. 240, а, общая таблица переходов имеет вид:
- 573 -
Из этой таблицы следует, что состояния из множества {0, 3, 4}являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинаковыми при замене цифры в числителе 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0,4} И {1,5}.
Объединяя эквивалентные состояния в автомате М>1, получаем эквивалентный автомат М>2 с меньшим числом состоянии, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы М>1 и М>2 являются эквивалентными, если каждому состоянию σ>i , автомата М>1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата M>2, и если каждому состоянию σ>j , автомата М>2 соответствует хотя бы одно эквивалентное ему состояние автомата М>1.
Эквивалентные состояния, например, σ>i и σ>j , удобно объединять по общей таблице переходов, вычеркивая строку σ>j , и заменяя везде в числителе числа σ>j на σ>i . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состоянии. Так, для рассматриваемого примера получаем последовательно: