Распознавание строк конечным автоматом

ОпределениеПара (q, t) Î Q´T^*, где t - текущий остаток входной строки, называется конфигурацией автомата М.

ОпределениеКонфигурация (q₀, t), где t - полная входная строка, называется начальной, а пара (q, e), где q Í Z, называется заключительной конфигурацией.

Шаг работы автомата можно представить отношением непосредственного следования конфигураций |-. Тогда, если F(q, t)=p, где pÎ Q, то можно записать (q, tt) |- (p, t) для всех t Î T^*. Эта запись означает то, что если автомат находится в состоянии q и входная головка обозревает входной символ t, то автомат может делать шаг, за который он переходит в состояние p и сдвигает головку на одну ячейку вправо.

ОпределениеАвтомат М допускает (принимает) строку t, если существует путь по конфигурациям (q, t) |- (q, e) для некоторого q Î Z.

ОпределениеЯзык L, принимаемый конечным автоматом М, формально определяется как множество:

L(M) = {t | t Î T^* и (q, t) |- (q, e) для некоторого q Î Z}.

Существуют следующие способы представления функции переходов:

- командный способ. Каждую команду КА записывают в форме , где .

- табличный способ. Строки таблицы переходов соответствуют входным символам автомата t Î T, а столбцы – состояниям Q. Ячейки таблицы заполняются новыми состояниями, соответствующими значению функции . Неопределенным значениям функции переходов соответствуют пустые ячейки таблицы.

- графический способ.Строится диаграмма состояний автомата – неупорядоченный ориентированный помеченный граф. Вершины графа помечены именами состояний автомата. Дуга ведет из состояния в состояниe и помечается списком всех символов t Î T, для которых . Вершина, соответствующая входному состоянию автомата, снабжается стрелкой. Заключительное состояние на графе обозначается двумя концентрическими окружностями.