Русская Википедия:Конечный автомат с выходом

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

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

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

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

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

Литература

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