Автоматное преобразование информации

Не все окружающие нас преобразователи информации выполняют функциональ­ное отображение информации. Результат преобразования вход => выход зачастую зависит не только от того, какая информация в данный момент появилась па вхо­де, но и от того, что происходило раньше, от предыстории преобразования. Множе­ство примеров тому дают биологические системы. Например, один и тот же вход — извинение соседа после того, как он наступил вам на ногу в переполненном трам­вае — вызовет у вас одну реакцию в первый раз и совсем другую — в пятый раз. По-видимому, ваша реакция будет различной, она будет зависеть от предыдущих со­бытий, произошедших в трамвае, от входной истории.

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

Число возможных входных историй бесконечно (счетно), даже если различных элементов входной информации у автомата конечное число (как в конечном функ­циональном преобразователе). Если автомат по-разному будет себя вести для каж­дой возможной предыстории, то такой «бесконечный* автомат должен иметь бес­конечный ресурс — память, чтобы все эти предыстории как-то запоминать. Введем па множестве предыстории отношение.-эквивалентности. Две предыстории будем считать эквивалентными, если они одинаковым образом влияют на дальнейшее поведение автомата. Очевидно, что для своего функционирования автомат дол­жен не обязательно запоминать входные истории, достаточно, чтобы автомат за­поминал класс эквивалентности, к которому принадлежит данная история.

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

Определение 3.1. (Внутренним) состоянием автомата назовем класс эквивалент­ности его входных историй.

В своих состояниях автомат запоминает свое «концентрированное прошлое». Не­формально состояние системы — это ее характеристика, однозначно определяю­щая ее дальнейшее поведение, все последующие реакции системы на внешние со­бытия. На один и тот же входной сигнал конечный автомат может реагировать по-разному, в зависимости от того, в каком состоянии он находится в данный момент.

Поскольку состояние представляет собой класс эквивалентных предыстории вхо­дов, состояние может измениться только при приходе очередного входного сигна­ла. При получении входного сигнала конечный автомат не только выдает инфор­мацию на выход как функцию этого входного сигнала и текущего состояния, по и меняет свое состояние, поскольку входной сигнал изменяет предысторию. Функ­ционирование автомата удобно представлять графически. На рис. 3.1 блок памяти автомата хранит информацию о текущем состоянии S, которое вместе с входным сигналом X определяет выходную реакцию автомата У и следующее состояние S'.

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

Итак, конечный автомат — это устройство, работающее в дискретные моменты времени (такты). На вход конечного автомата в каждом такте поступает один из возможных входных сигналов, а на его выходе появляется выходной сигнал, явля­ющийся функцией его текущего состояния и поступившего входного сигнала. Внут­реннее состояние автомата также меняется. Моменты срабатывания (такты) опре­деляются либо принудительно тактирующими синхросигналами, либо асинхрон­но, наступлением внешнего события — прихода сигнала.

Определим конечный автомат формально.

Определение 3.2. Конечным автоматом Мили называется шестерка объектов: А = <S, X, Y, s₀, d, l>, где:

S — конечное непустое множество (состояний);

X — конечное непустое множество входных сигналов (входной алфавит);

Y — конечное непустое множество выходных сигналов (выходной алфавит);

s₀ Î S — начальное состояние;

d: S x X —> S — функция переходов;

l: S x X —> Y — функция выходов.

Кроме графического представления для автомата можно использовать и таблич­ное, задавая функции переходов и выходов в виде таблиц.