Конечный автомат с выходом

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

ОпределениеПравить

Существуют различные способы задания конечного автомата с выходом. Например, конечный автомат с выходом может быть задан в виде упорядоченной семерки[1]:  , где

  •   — входной алфавит (его элементы — входные символы);
  •  выходной алфавит (его элементы — выходные символы);
  •   — конечное множество состояний конечного автомата с выходом;
  •   — начальное состояние конечного автомата с выходом;
  •   — непустое множество заключительных состояний, каждый элемент которого называют заключительным состоянием конечного автомата с выходом;
  •   — отображение функция переходов,  ;
  •   — отображение функция выходов,  .

Функция   называется ограниченно детерминированной функцией.

Задача структурного синтезаПравить

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

ПримечанияПравить

ЛитератураПравить

  • Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 743 с. — ISBN 5-7038-2886-4.