Конечный автомат с выходом — разновидность детерминированного конечного автомата, дополненная выходным алфавитом и функцией выходов.
Определение Существуют различные способы задания конечного автомата с выходом. Например, конечный автомат с выходом может быть задан в виде упорядоченной семерки элементов некоторых множеств: , где — входной алфавит (его элементы — входные символы); — выходной алфавит (его элементы — выходные символы); — множество состояний конечного автомата с выходом; — начальное состояние конечного автомата с выходом; — непустое множество заключительных/конечных состояний, каждый элемент которого называют заключительным/конечным состоянием конечного автомата с выходом; — отображение функция переходов, ; — отображение функция выходов, .
Функция называется ограниченно детерминированной функцией.
Задача структурного синтеза Эта задача аналогична задаче реализации булевой функции схемой из функциональных элементов. В отличие от схемы из функциональных элементов для реализации булевой функции, эта схема должна содержать элементы задержки, позволяющие хранить информацию о текущем состоянии автомата. Для решения задачи структурного синтеза составляется таблица для функций переходов и выходов конечного автомата с выходом, затем строится структурная таблица, в которой каждый входной и выходной символ и каждое состояние заменяются их двоичным кодом и которая задает булев оператор.
Примечания
Литература
Категория:Конечные автоматы Категория:Формальные методы