6-8. СВЯЗЬ МЕЖДУ ВРЕМЕННЫМИ ФУНКЦИЯМИ И КОНЕЧНЫМИ АВТОМАТАМИ

Модель конечного автомата, рассмотренная нами в § 6-6, позволяет описывать схемы, работа которых описывается как с помощью ВБФ, так и с помощью РБФ. Таким образом, модель конечного автомата обладает весьма универсальными свойствами. Покажем истинность этого утверждения. Начнем с рассмотрения задачи о сведении любой ВБФ к паре автоматных функций вида (6-32). Пусть мы имеем некоторую ВБФ

Возьмем вектор с компонентами, где Каждую из функций закодируем некоторым вектором вида где есть либо либо Зададим теперь следующее соответствие. Если вектор кодирует а вектор кодирует то Если же и ВБФ периодическая, то где вектор, кодирующий то. Если же и ВБФ непериодическая, то Полученное соответствие имеет в общем случае вид:

Сравнивая полученные соотношения с векторной формой задания конечного автомата (6-32), можно убедиться, что ВБФ сведена к частному виду автоматных функций. При этом функция переходов автомата не зависит от

Пример 6-19. Осуществить переход от ВБФ

к конечному автомату.

Введем двухкомяонентный вектор Поставим в соответствие то, векторы Построим автоматные таблицы

Рис. 6-23. (см. скан)

На рис. 6-23 показана минимизация полученных функций. После минимизации получаем:

На рис. 6-24,а показана реализация исходной ВБФ с помощью переключателя. Так как исходная ВФБ не предполагалась периодической, то переключатель, дойдя до положения 2, должен остановиться. На рис. 6-24, б показана реализация полученных после минимизации

Рис. 6-24. (см. скан)

функций с помощью задержек в цепях обратной связи. Читателю предлагается сравнить сложность этих реализаций с учетом оценки сложности реализации переключателя, приведенной в гл. 5.

Рассмотрим теперь сведение РБФ-2 к конечному автомату. Пусть задана некоторая РБФ-2

Легко видеть, что с помощью -мерного вектора можно записать эту функцию в следующей эквивалентной форме:

От нее легко перейти к записи в виде векторных функций конечного автомата (6-32):

Из сравнения (6-32) и (6-34) вытекает, что с помощью РБФ-2 описываются конечные автоматы, у которых функция перехода описывается всегда некоторым стандартным образом.

Заметим, наконец, что теорема 6-3 устанавливает тесную связь между РБФ-1 и конечными автоматами. Совсем очевидно, что любая РБФ-1 может быть реализована в виде конечного автомата.

Таким образом, модель конечного автомата оказывается универсальной в классе временных схем,