ВВЕДЕНИЕ

Введем основные понятия, на которых будет базироваться дальнейшее изложение.

Рассмотрим некоторое устройство (рис. В-1 ,а) - с входами и выходами, на каждый вход которого может быть подан произвольный символ из конечного алфавита

называемого входным алфавитом.

Совокупность символов, поданных на вход устройства, образует входное слово над алфавитом X нашего устройства. Один из символов алфавита X (например, ) соответствует пустому символу. Если на некоторый вход устройства подается символ то физически это означает отсутствие какого-либо возбуждения устройства по данному входу.

На выходе устройства появляются выходные слова, составленные из символов выходного алфавита:

В силу конечности алфавитов X и Y и входных и выходных слов (длина входного слова всегда равна , а выходного — ) общее число различных входных и выходных слов конечно.

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

Рис. В-1.

Пусть работа устройства полностью определяется лишь входным словом. Тогда работа такого устройства будет определена, если мы зададим следующую таблицу соответствия для всех входных слов

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

Определение Устройство, условия работы которого описываются при помощи соответствия называется конечным автоматом без памяти, или комбинационной схемой.

Автомат такого типа может рассматриваться как устройство, производящее кодирование слов над алфавитом X словами над алфавитом Очевидно, что декодирование при этом не всегда возможно.

Конечные автоматы без памяти являются наиболее простыми логическими устройствами дискретного типа. Рассмотрению методов анализа и синтеза подобных автоматов посвящена первая часть настоящей книги.

Рассмотрим автомаш более сложной природы. Зададимся конечным алфавитом

который назовем алфавитом внутренних состояний. Символы будем называть в нутре а ними состояниями (состояниями).

Предположим, что работа устройства полностью определяется входным словом и внутренним состоянием, в котором находится устройство в определенный такт работы.

Пара однозначно определяет выходное слово и внутреннее состояние, в которое устройство перейдет в следующий такт. Работа такого устройства полностью

определена, если заданы две таблицы А и В следующего вида:

Первая таблица определяет выходное слово, соответствующее паре а вторая — определяет внутреннее состояние устройства в следующий такт.

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

Такой автомат изображен на рис.

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

Естественным обобщением таких детерминированных автоматов являются автоматы стохастического типа. В таких автоматах вместо однозначного соответствия

задается лишь вероятность замены на или на

Эта вероятность для случая автомата без памяти задается с помощью стохастической матрицы

Элемент в этой матрице определяет вероятность появления слова на выходе автомата, если на его вход подано слово При этом

В случае автомата с памятью такие матрицы задаются для каждого столбца таблицы А и каждого столбца таблицы В.

Стохастические автоматы в настоящее время изучаются весьма интенсивно; теория таких автоматов находится в состоянии становления. Рассмотрение методов анализа и синтеза стохастических автоматов требует особого аппарата и выходит за рамки настоящей работы.

Мы пока не накладывали никаких ограничений на природу символов, образующих алфавиты и Теперь потребуем, чтобы эти символы были бы закодированы в числовой форме.

Для большего удобства рассуждений и возможностей логического анализа и синтеза схем автоматов мы чаще всего будем предполагать, что символы алфавитов X, Y и закодированы двоичным кодом. Это означает, что каждый символ алфавита состояний входного и выходного алфавитов соответствует некоторому слову из алфавита:

Рассмотрим пример такого кодирования. Пусть алфавит состоит из трех символов, представляющих собой цвета: желтый, синий и красный, и пусть алфавит состоит из шести символов, также представляющих собой цвета: желтый, синий, красный, зеленый, оранжевый и фиолетовый.

Устройство, перерабатывающее цвета, является конечным автоматом без памяти, с двумя входами и одним выходом. Это устройство отображает всевозможные слова длиной в два символа над алфавитом X в слова длиной в один символ над алфавитом У. Зададим теперь

Таблицу соответствия в следующей форме:

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

Для нумерации символов алфавитов X и сопоставим каждому из цветов десятичное число от 0 до Тогда таблица соответствия примет следующий вид:

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

Двоично-кодированная таблица соответствия имеет вид:

Видно, что двоичное кодирование алфавитов X и сводится к увеличению длины слов, поступающих на вход автомата и выдаваемых на его выходе.

Минимальное число двоичных разрядов, которое необходимо затратить при двоичном кодировании символов из алфавитов X и определяется из следующего соотношения:

где — число символов в алфавите (т. е. общее число различных символов алфавитов X и означает целую часть

Таким образом, путем соответствующего кодирования автомат с произвольным входным и выходным алфавитом может быть приведен к автомату с двоичным входом и выходом. Однако этот новый автомат должен оперировать со словами входного и выходного алфавита, длина которых больше длин соответствующих слов исходного автомата. Если для автомата с алфавитом X, состоящим из символов, и алфавитом У, состоящим из I символов, длина слов на входе и выходе равна соответственно и то для эквивалентного ему двоичного автомата допустимая длина слов на входе и на выходе равна соответственно где величина определяется на основании соотношения (В-2).

В первой и во второй частях настоящей работы рассматриваются методы анализа и синтеза двоичных автоматов. В третьей части рассматриваются аналогичные проблемы для автоматов, у которых произведено лишь цифровое, но не обязательно двоичное кодирование алфавитов X и