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

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

Определение

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга