Конечный автомат

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

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: $~M = (Q, \Sigma, \delta, q_0, F)$, где:

• Q — множество состояний автомата;
• q₀ — начальное (стартовое) состояние автомата ($q_0 \in Q$);
• F — множество заключительных (или допускающих) состояний, таких что $F \subseteq Q$;
• Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
• δ — заданное отображение множества $Q \times \Sigma$ во множество $\mathcal {P} (Q)$ подмножеств Q: $\delta : Q \times \Sigma \rightarrow \mathcal {P} (Q)$ (иногда δ называют функцией переходов автомата).

Автомат начинает работу в состоянии q₀, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается».

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

Другие способы описания

1. Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, ребра — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.
2. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ.

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированный конечный автомат

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

Существуют переходы, помеченные пустой цепочкой ε	Из одного состояния выходит несколько переходов, помеченных одним и тем же символом

Если рассмотреть случай, когда автомат задан следующим образом: $~M = (Q, \Sigma, \delta, S, F)$, где:

• S — множество стартовых состояний автомата, такое что $S \subseteq Q$;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата $~M$.

Существует теорема, гласящая, что «Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали» (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

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

Автоматы и регулярные языки

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

Теорема Клини гласит, что класс языков, представимых конечными автоматами, совпадает с классом регулярных языков. Кроме того, этот класс совпадает с классом языков, задаваемых регулярными грамматиками.

Специализированные языки программирования

• Язык последовательных функциональных схем SFC (Sequential Function Chart) — графический язык программирования широко используется для программирования промышленных логических контроллеров (ПЛК).

В SFC программа описывается в виде схематической последовательности шагов, объединенных переходами.

Разработка моделей с использованием конечных автоматов

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

Примечания

См. также

• Автоматное программирование
• Sequential Function Chart
• Компилятор
• Транслятор
• Сети Петри
• Секвенциальная логика (Последовательностная логика)
• Таблица принятия решений

Ссылки

• М. И. Дехтярь Введение в схемы, автоматы и алгоритмы
• Open source генератор конечных автоматов на языках C++ и Java по XML файлам описания
• Недетерминированные конечные автоматы
• С. Ю. Подзоров Курс лекции по теории алгоритмов
• Теория автоматов / Э. А. Якубайтис, В. О. Васюкевич, А. Ю. Гобземис, Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109–188. — URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
• Применение конечных автоматов для решения задач автоматизации
• Пример реализации конечного автомата на языке Python для фреймворка Django
• Пример реализации конечных автоматов на языке С++

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 13 мая 2011.