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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

  • V — входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;
  • Q — множество состояний;
  • q_0 — начальное состояние (q_0 \in Q);
  • F — множество заключительных состояний (F \subset Q);
  • \delta — функция переходов, определенная как отображение \delta : Q \times ( V \cup \{ \lambda \} ) \rightarrow 2^Q, такое, что \delta(q,a) = \{ r : q \rightarrow_a r \}, т.е. значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).

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

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

Другие способы описания[править | править исходный текст]

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

Детерминированность[править | править исходный текст]

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

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

Если рассмотреть случай, когда автомат задан следующим образом: ~M = (V, Q, S, F, \delta), где S — множество начальных состояний автомата, такое, что S \subseteq V, то появляется третий признак недетерминированности - наличие нескольких начальных (стартовых) состояний у автомата ~M.


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

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

Автоматы и регулярные языки[править | править исходный текст]

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

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

Специализированные языки программирования[править | править исходный текст]

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

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

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

Примечания[править | править исходный текст]

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]