[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

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

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

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

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

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

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

Рис. 1. Автоматный преобразователь и его реализация

Пример 1:
Опишем поведение родителя, отправившего сына в школу. Сын приносит двойки и пятерки. Отец не хочет хвататься за ремень каждый раз, как только сын получит очередную двойку, и выбирает более тонкую тактику воспитания. Задавать автомат удобно графом, в котором вершины соответствуют состояниям, а ребро из состояния s в состояние q, помеченное х/у, проводится тогда, когда автомат из состояния s под воздействием входного сигнала х переходит в состояние q с выходной реакцией у. Граф автомата, моделирующего умное поведение родителя, представлен на рис. 2.

Рис. 2. Автомат, описывающий поведение "умного" отца

Этот автомат имеет четыре состояния (s0, s1, s2, s3} и два входных сигнала - оценки, полученные сыном в школе: (2,5}. Начиная с начального состояния s0 (оно помечено входной стрелкой), автомат под воздействием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы - реакции на входы. Выходы автомата {у0,..., у5} будем интерпретировать как действия родителя так:
у0: - брать ремень;
y1:- ругать сына;
у2: - успокаивать сына;
уЗ: - надеяться;
у4: - радоваться;
у5: - ликовать.

Сына, получившего одну и ту же оценку - двойку, ожидает дома совершенно различная реакция отца в зависимости от предыстории его учебы. Отец помнит, как его сын учился раньше, и строит свое воспитание с учетом его предыдущих успехов и неудач. Например, после третьей двойки в истории 2,2,2 сына встретят ремнем, а в истории 2, 2, 5, 2 - будут успокаивать. Каждая предыстория определяет текущее состояние автомата, при этом некоторые входные предыстории эквивалентны (именно те, которые приводят автомат в одно и то же состояние): история 2,2,5 эквивалентна пустой истории, которой соответствует начальное состояние.

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

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

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

Определение 2.
Конечным автоматом Мили называется шестерка объектов: А = <S, X, Y, s0,, >, где: S - конечное непустое множество (состояний); X - конечное непустое множество входных сигналов (входной алфавит); Y - конечное непустое множество выходных сигналов (выходной алфавит); s0 S - начальное состояние; : SxX S - функция переходов; : SxX Y - функция выходов.

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

Таблица 1
а)

	2	5
s0	s1	s3
s1	s2	s0
s2	s2	s0
s3	s1	s3

б)

	2	5
s0	y2	y4
s1	y1	y3
s2	y0	y3
s3	y2	y5

Таблица 3.1, а определяет функцию переходов так: (s0, 2) = s1; (s2,5) = s0..,
а табл. 3.1, б определяет функцию выходов : (s0, 2) = у2; (s2, 5) = уЗ..,

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]