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

Определение

Существуют различные способы задания конечного автомата с выходом. Например, конечный автомат с выходом может быть задан в виде упорядоченной семерки элементов некоторых множеств : ${\displaystyle M=(V,W,Q,q_{0},F,\delta ,\mu )}$ , где

• ${\displaystyle V}$ — входной алфавит (его элементы — входные символы );
• ${\displaystyle W}$ — выходной алфавит (его элементы — выходные символы );
• ${\displaystyle Q}$ — множество состояний конечного автомата с выходом;
• ${\displaystyle q_{0}}$ — начальное состояние конечного автомата с выходом;
• ${\displaystyle F}$ — непустое множество заключительных/конечных состояний , каждый элемент которого называют заключительным/конечным состоянием конечного автомата с выходом;
• ${\displaystyle \delta }$ — отображение функция переходов , ${\displaystyle \delta :Q\times V\rightarrow Q}$ ;
• ${\displaystyle \mu }$ — отображение функция выходов , ${\displaystyle \mu :Q\times V\rightarrow W}$ .

Функция ${\displaystyle V^{*}\rightarrow W^{*}}$ называется ограниченно детерминированной функцией.

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

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

Примечания

Литература

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