Определение конечного автомата

Конечный автомат – это простейший распознаватель без вспомогательной памяти. Он является эффективным способом определения регулярных языков.

Определение Детерминированным конечным автоматом (ДКА) называется пятерка объектов:

,

где - конечное множество состояний автомата;

- конечное множество допустимых входных символов;

- функция переходов, отображающая множество Q´T во множество Q;

- конечное множество начальных состояний автомата;

Z - множество заключительных состояний автомата, Z Í Q.

Определение Недетерминированным конечным автоматом (НКА) называется конечный автомат, в котором в качестве функции переходов используется отображение во множество всех подмножеств множества состояний автомата , т.е. функция переходов неоднозначна, так как текущей паре соответствует множество очередных состояний автомата .