Синтез конечных автоматов

Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x(n) и s(n) в выходные переменные y(n) и s(n+1) в соответствии с заданными характеристическими s(n+1)= d(x(n), s(n)) и y(n) = l(x(n), s(n)). Для сохранения состояний s(n+1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.

При реализации автоматов в двоичном структурном алфавите можно использовать методы синтеза комбииационных схем. Но для этого необходимо закодировать состояния схемы и предоставить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, Y и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, заданного графом на рис. 2, таблицу переходов можно преобразовать к виду (табл. 5).

Таблица 5

Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s(n+1) и y(n) представлены двоичными кодами (табл. 6).

Таблица 6

x(n){

s(n){

s(n+1) {

y(n){y1(n)

Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x₁(n), x₂(n) и переменным состояния s₁(n), s₂(n), а также три выхода, соответствующие переменным состояния s₁(n+1), s₂(n+1) и выходной переменной y₁(n). Синтезировав комбинационную схему, соответствующую полученной таблице, и введя два элемента задержки З₁ и З₂,получим структурную схему автомата (рис. 5).

Рис. 5