Введение. 
Моделирование работы конечного распознавателя

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

Существуют различные способы задания конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки:

M = (V, Q, q0, F, в),.

где.

• · V — входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;
• · Q — множество состояний;
• · q0— начальное состояние ;
• · F — множество заключительных состояний ;
• · в — функция переходов, определенная как отображение

.

такое, что.

.

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

Конечный автомат начинает работу в состоянии q0, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.

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

Учебная цель. Получение практических навыков построения моделей конечных распознавателей.

Теоретическая справка.

Недетерминированный конечный автомат (НКА) — это пятерка.

M = (Q, T, D, q0, F),.

где.

• · Q — конечное множество состояний;
• · T — конечное множество допустимых входных символов (входной алфавит);
• · D — функция переходов (отображающая множество QЧ (T{e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;
• · q0 Q — начальное состояние управляющего устройства;
• · F Q — множество заключительных состояний.

Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 1).

Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.

Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние, и не может делать переходы по e.

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