1-9. НЕКОТОРЫЕ ВЫВОДЫ ПРИКЛАДНОГО ХАРАКТЕРА

Во введении мы рассматривали принцип работы конечного автомата без памяти (рис. Такой автомат полностью определялся заданием конечной таблицы соответствия входных слов - выходным словам Как было указано, можно рассматривать случай, когда слова и представляют собой двоичные слова, соответственно поступающие на вход автомата и снимаемые с его выходов. В этом случае работа автомата может быть полностью описана с помощью следующей системы функции алгебры логики:

Здесь

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

Проблема полноты, рассмотренная в предыдущем параграфе, эквивалентна проблеме выбора стандартного набора логических элементов, из которых будет строиться автомат. При этом все функция системы (1-37) будут заменяться аналитическим выражением через базисные функции. Если, например, за базис выбраны функции отрицания, дизъюнкции и конъюнкции, что соответствует выбору стандартного набора логических элементов, состоящего из элементов трех Типов, то все функции из (1-37) могут быть представлены в ДСНФ или КСНФ и после этого реализованы на стандартных элементах. Уменьшение числа функций, входящих в базис, соответствует уменьшению числа различных логических элементов, принятых за стандартные.

Однако следует учитывать и другую сторону вопроса. При реализации автомата важно не только количество типов стандартных элементов, но и общее число их, затраченное на построение автомата. При этом сложность автомата с точки зрения количества использованных элементов существенно зависит от вида функций (1-37) и вида функций, выбранных в качестве базиса. Возникает задача о «простейшем» представлении функций из системы (1-37) через систему базисных функций. Решению этой проблемы посвящена следующая глава книги.