Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбина­цией значений переменных на входах в данный момент времени

КОНЕЧНЫЕ АВТОМАТЫ

В контактных и логических схемах значения выходных переменных определяются только комбина­цией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значений входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.

Пусть X_i - алфавит входной переменной х_i, a Y_j - алфавит выходной переменной у_j. Конечный автомат с п входами и т выхо­дами характеризуется входным алфавитом и выходным алфавитом , причем символами входного алфавита служат слова длины п, а символами выходного алфавита - слова длины т, где . Особого внимания заслу­живают конечные автоматы с двузначным структурным алфави­том, зависимости между входными и выходными переменными которых выражаются булевыми функциями. Их значение обуслов­лено тем, что любая информация может быть представлена в двоич­ных кодах. В то же время при технической реализации автоматов используются преимущественно двоичные элементы и двузначная логика.

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окон­чания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвле­каются от существа этих процессов и считают, что переменные изме­няются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть раз­личными, но без потери общности их можно считать равными . Предполагается, что тактовые моменты определя­ются синхронизирующими сигналами. Таким образом, вводится по­нятие дискретного автоматного времени (v = 1, 2,...), причем переменные зависят не от физического времени, а от номера такта v, т. е. вместо непрерывных функции рассматриваются дискрет­ные значения х (v).