7.6. Задачи абстрактной теории конечных автоматов

Задача анализа автомата заключается в следующем: Задан конечный автомат M=(A, B, Q, Ф) и задано его начальное состояние q принадлежит Q. Требуется найти регулярное выражение для события S, представленного в этом автомате выходным сигналом b принадлежащим B.

Согласно теореме Клини это задание всегда имеет решение.

Задача синтеза автомата заключается в формировании множества состояний Q=(q1,….qi) и в построении функции переходов и функции выходов по заданному поведению автомата в виде регулярных выражений.

Эта задача, как и задача анализа, для конечного автомата всегда имеет решение.