Введение в схемы, автоматы и алгоритмы



             

Переработка информации с помощью конечных автоматов


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

Автомат

Автомат

На такие устройства в последовательные дискретные моменты времени 1,2, …, t, t+1,… поступают входные сигналы x(1),x(2), …, x(t),x(t+1),… и в ответ на них автомат A вырабатывает выходные сигналы y(1) y(2), …, y(t), y(t+1),…. Конечные автоматы характеризуются двумя особенностями.

  1. Отсутствие предвосхищения: выходной сигнал y(t), выдаваемый автоматом в момент t, зависит лишь от полученных к этому времени входов x(1),x(2), …, x(t), т.е. автомат не может предвосхитить будущие входы и заранее на них отреагировать. Таким образом, имеется некоторая функция выходов
    (x(1),x(2), …, x(t))= y(t), определяющая очередной выход по предшествующему входу.
  2. Конечная память: в каждый момент t информация в автомате о полученном к этому моменту входе x(1),x(2), …, x(t) конечна. Это свойство удобно интерпретировать следующим образом: автомат имеет конечное множество состояний Q и в каждый момент находится в одном из этих состояний. При получении очередного входа состояние может измениться. Таким образом, состояние q
    Q, в котором находится автомат после получения входной последовательности x(1),x(2), …, x(t), и представляет информацию об этой последовательности, используемую в дальнейшей работе автомата при определении следующего состояния и выхода.

Наше обсуждение приводит к следующему определению конечного автомата с выходом.

Определение 4.1. Конечный автомат - преобразователь - это система вида

A = <\Sigma_X, \Sigma_Y, Q, q_0, \Phi, \Psi>

включающая следующие компоненты:

  • ?X={a1, … , am} (m
    1) - конечное множество - входной алфавит;
  • ?Y={b1, … , br} (r
    1) - конечное множество - выходной алфавит;
  • Q={q0, … , qn-1} (n
    1) - конечное множество - алфавит внутренних состояний;
  • q0
    Q - начальное состояние автомата;
  • ?: Q ? ?X
    Q - функция переходов, ?(q, a) - это состояние, в которое переходит автомат из состояния q, когда получает на вход символ a;
  • : Q ? ?X
    ?Y - функция выходов,
    (q, a) - это символ из ?Y, который выдает на выход автомат в состоянии q, когда получает на вход символ a.




Содержание    Вперед