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

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

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

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

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

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

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

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

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

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