Страница 30 из 32
6. Синтез конечных автоматов. Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x(ν) и s(ν) в выходные переменные y(ν) и s(ν + 1) в соответствии с заданными характеристическими функциями s(ν + 1) = δ (x(ν), s(ν)) и y(ν)= λ (x(ν), s(ν)). Для сохранения состояний s(ν + 1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.
При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза
- 571 -
комбинационных схем. Но для этого необходимо закодировать состояния схемы н представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, Y и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, заданного в (4), таблицу переходов можно преобразовать к виду:
Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s(ν + 1) и у(ν) представлены двоичными кодами:
Рис. 239. Структурная схема конечного автомата
Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x1(ν), х2(ν) и переменным состояния s(ν), s2(ν), а также три выхода, соответствующие переменным состояния s1(ν + 1), s2(ν + 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 соответствует, по крайней мере, одно эквивалентное ему состояние автомата M2, и если каждому состоянию σj , автомата М2 соответствует хотя бы одно эквивалентное ему состояние автомата М1.
Эквивалентные состояния, например, σi и σj , удобно объединять по общей таблице переходов, вычеркивая строку σj , и заменяя везде в числителе числа σj на σi . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состоянии. Так, для рассматриваемого примера получаем последовательно:
- 574 -
Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.240, б).
8. Эквивалентное разбиение. Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S1, S2 ..., Sν}. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через σ'0, σ'1, ..., σ'ν представители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S' = {σ'0, σ'1, ..., σ'ν}. Можно утверждать, что автоматы М и М' эквивалентны (М ~ М'), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.