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

Пример детерминированного конечного автомата, который принимает только двоичные числа, делящиеся на три. Состояние S₀ является одновременно и начальным состоянием, и конечным состоянием. Например, строка «1001» приводит к последовательности состояний S₀, S₁, S₂, S₁, S₀, а потому принимается.

Детерминированный конечный автомат (ДКА, DFA, англ. deterministic finite automaton, DFSA, англ. deterministic finite-state automaton, DFSM англ. deterministic finite-state machine), известный также как детерминированный конечный распознаватель — это конечный автомат, принимающий или отклоняющий заданную строку символов путём прохождения через последовательность состояний, определённых строкой^[1]. Имеет единственную последовательность состояний во время работы. Мак-Каллок и Уолтер Питтс были одними из первых исследователей, предложивших концепцию, похожую на конечный автомат в 1943 году^[2][3].

Рисунок иллюстрирует детерминированный конечный автомат с помощью диаграммы состояний. В этом примере имеется три состояния — S₀, S₁ и S₂ (отражены на рисунке окружностями). Автомат на вход принимает конечную последовательность нулей и единиц. Для каждого состояния существует стрелка перехода, ведущая из состояния в другое состояние как для 0, так и для 1. После чтения символа, ДКА детерминированно переходит из одного состояния в другое, следуя по стрелке перехода. Например, если автомат находится в состоянии S₀, а входным символом является 1, то автомат детерминированно переходит в состояние S₁. ДКА имеет начальное состояние (графически показывается стрелкой «из ниоткуда»), откуда начинается вычисление, и множество конечных состояний (обозначаемых графически в виде двойной окружности), которые определяют, успешно ли закончились вычисления.

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

ДКА распознаёт в точности множество регулярных языков^[1], которые, среди прочего, полезны для лексического анализа и сопоставления с образцом. ДКА могут быть построены из недетерминированного конечного автомата (НКА, англ. nondeterministic finite automata, NFAs) с помощью сведения НКА к ДКА^[англ.].

Формальное определение

Детерминированный конечный автомат ${\displaystyle M}$ является 5-кортежем ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$, состоящим из

• конечное множество состояний ${\displaystyle Q}$
• конечное множество входных символов, называемое алфавитом ${\displaystyle \Sigma }$
• функция переходов ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$
• начальное состояние ${\displaystyle q_{0}\in Q}$
• множество конечных состояний ${\displaystyle F\subseteq Q}$

Пусть ${\displaystyle w=a_{1}a_{2}...a_{n}}$ — строка над алфавитом ${\displaystyle \Sigma }$. Автомат ${\displaystyle M}$ принимает строку ${\displaystyle w}$, если последовательность состояний ${\displaystyle r_{0},r_{1},...,r_{n}}$ существует в ${\displaystyle Q}$ со следующими условиями

1. ${\displaystyle r_{0}=q_{0}}$
2. ${\displaystyle r_{i+1}=\delta (r_{i},a_{i+1})}$, для ${\displaystyle i=0,...,n-1}$
3. ${\displaystyle r_{n}\in F}$.

Словами, первое условие говорит, что машина начинает работу с состояния ${\displaystyle q_{0}}$. Второе условие говорит, что для данного символа строки ${\displaystyle w}$ машина переходит из состояния в состояние согласно функции переходов ${\displaystyle \delta }$. Последнее условие говорит, что машина принимает ${\displaystyle w}$, если последний входной символ строки ${\displaystyle w}$ вынуждает машину перейти в одно из конечных состояний. В противном случае говорят, что автомат отвергает строку. Множество строк, которые принимает ${\displaystyle M}$, является языком, распознаваемым автоматом ${\displaystyle M}$, и этот язык обозначается ${\displaystyle L(M)}$.

Детерминированный конечный автомат без конечных состояний и без начального состояния известен как система переходов^[англ.] или полуавтомат^[англ.].

Для более полного формального определения см. статью «Теория автоматов».

Полные и неполные автоматы

Согласно вышеприведённому определению, детерминированные конечные автоматы всегда полные — они определяют переход для каждого состояния и для каждого входного символа.

В то время, как используемое определение является наиболее общепринятым, некоторые авторы используют термин детерминированный конечный автомат для слегка другого понятия — автомата, который определяет самое большее один переход (а не в точности один как в вышеприведённом определении) для каждого состояния и каждого входного символа. Функции перехода позволяется быть частично определенной^[англ.]. Если переход не определён, автомат останавливается.

Пример

Следующий пример является ДКА ${\displaystyle M}$ с двоичным алфавитом, который требует, чтобы вход содержал чётное число нулей.

Диаграмма состояний для M

${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$ где

• ${\displaystyle Q=\{S_{1},S_{2}\}}$
• ${\displaystyle \Sigma =\{0,1\}}$
• ${\displaystyle q_{0}=S_{1}}$
• ${\displaystyle F=\{S_{1}\}}$ и
• ${\displaystyle \delta }$ определяется следующей таблицей переходов^[англ.]:

	0	1
S1	S2	S1
S2	S1	S2

Конечное состояние ${\displaystyle S_{1}}$ соответствует чётному числу нулей во входной строке, в то время как ${\displaystyle S_{2}}$ говорит о нечётном числе. 1 во входном потоке не изменяет состояние автомата. Когда входная строка заканчивается, конечное состояние покажет, содержала ли входная строка чётное число нулей, или нет. Если входная строка содержит чётное число нулей, ${\displaystyle M}$ закончит в конечном состоянии ${\displaystyle S_{1}}$, так что входная строка будет принята.

Язык, распознаваемый ${\displaystyle M}$, является регулярным языком, определяемым регулярным выражением ((1*) 0 (1*) 0 (1*))*, где * является звездой Клини, например 1* означает любое число (возможно, равное нулю) последовательных единиц.

Свойства замкнутости

Автомат слева вверху распознаёт язык всех бинарных строк, содержащих по меньшей одну подстроку «00». Нижний автомат справа распознаёт все двоичные строки с чётным числом «1». Нижний левый автомат получается как производный из первых двух, он распознаёт пересечение обоих языков.

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

• Объединение
• Пересечение^[4] (см. рисунок)
• Конкатенация
• Дополнение
• замыкание Клини
• Обращение
• Итерация
• Разность
• Подстановка
• Гомоморфизм

Для каждой операции оптимальное построение с учётом числа состояний определяется в исследовании позиционной сложности^[англ.].

Поскольку ДКА эквивалентны^[англ.] недетерминированным конечным автоматам (НКА, англ. nondeterministic finite automata, NFA), эти замыкания могут быть доказаны с помощью свойств замыканий НКА.

Как моноид переходов

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

Для данного входного символа ${\displaystyle a\in \Sigma }$ можно построить функцию перехода ${\displaystyle \delta _{a}:Q\rightarrow Q}$ путём определения ${\displaystyle \delta _{a}(q)=\delta (q,a)}$ для всех ${\displaystyle q\in Q}$. (Этот приём называется каррированием.) В этом ракурсе ${\displaystyle \delta _{a}}$ «действует» на состояние Q с получением другого состояния. Можно рассматривать результат суперпозиции функций, последовательно применённых к различным функциям ${\displaystyle \delta _{a}}$, ${\displaystyle \delta _{b}}$ и так далее. Если дана пара букв ${\displaystyle a,b\in \Sigma }$, можно определить новую функцию ${\displaystyle {\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}}$, где ${\displaystyle \circ }$ обозначает суперпозицию функций.

Ясно, что этот процесс может быть рекурсивно продолжен, давая следующее рекурсивное определение ${\displaystyle {\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q}$:

${\displaystyle {\widehat {\delta }}(q,\epsilon )=q}$, где ${\displaystyle \epsilon }$ является пустой строкой, а

${\displaystyle {\widehat {\delta }}(q,wa)=\delta ({\widehat {\delta }}(q,w),a)}$, где ${\displaystyle w\in \Sigma ^{*},a\in \Sigma }$ и ${\displaystyle q\in Q}$.

Функция ${\displaystyle {\widehat {\delta }}}$ определена для всех слов ${\displaystyle w\in \Sigma ^{*}}$. Работа ДКА является последовательностью суперпозиций ${\displaystyle {\widehat {\delta }}}$ на себя.

Повторение суперпозиций функций образует моноид. Для функций перехода этот моноид известен как Моноид переходов^[англ.], или, иногда, как полугруппа преобразований. Построение может быть обращено — если дана ${\displaystyle {\widehat {\delta }}}$, можно реконструировать ${\displaystyle \delta }$, так что эти два описания эквивалентны.

Локальные автоматы

Локальный автомат — это ДКА, для которого все дуги с той же меткой ведут в одну вершину. Локальные автоматы принимают класс формальных языков^[англ.], для которых принадлежность слова к языку определяется «скользящим окном» длины два на слове^[5][6]

Граф Майхилла над алфавитом A — это ориентированный граф с множеством вершин A и подмножеством вершин, помеченных как «начальная» и «конечная». Язык, принимаемый графом Майхилла, является множеством ориентированных путей из начальной вершины в конечную — граф тогда работает как автомат^[5]. Класс языков, воспринимаемый графами Майхилла является классом локальных языков^[7].

Стохастика в ДКА

Когда начальное состояние и конечные состояния игнорируются, ДКА с ${\displaystyle n}$ состояниями и алфавитом размера ${\displaystyle k}$ можно рассматривать как орграф с ${\displaystyle n}$ вершинами, в котором все вершины имеют ${\displaystyle k}$ исходящих дуг с метками ${\displaystyle 1,\ldots ,k}$ (орграф с ${\displaystyle k}$ исходами). Известно, что когда ${\displaystyle k\geqslant 2}$ является фиксированным целым, с высокой вероятностью наибольшая компонента сильной связности (англ.  strongly connected component, SCC), в которой орграф с ${\displaystyle k}$ исходами выбран равномерно случайно, имеет линейный размер и может быть достигнут из любой вершины^[8]. Было также доказано, что при возрастании ${\displaystyle k}$ по мере роста ${\displaystyle n}$, весь орграф имеет фазовый переход к сильной связности подобно модели Эрдёша — Реньи для связности^[9].

В случайном ДКА максимальное число вершин, достижимых из одной вершины с высокой вероятностью очень близко к числу вершин в наибольшей компоненте сильной связности^[8][10]. Это также верно для наибольшего порождённого подграфа с минимальной полустепенью захода единица, который можно рассматривать как ориентированную версию ${\displaystyle 1}$-ядра^[9].

Преимущества и недостатки

ДКА является одной из наиболее практичных моделей вычислений, поскольку существует тривиальный онлайн алгоритм^[англ.] линейного времени и постоянной памяти для моделирования ДКА на входном потоке. Имеются также эффективные алгоритмы поиска распознавания ДКА:

• дополнение языка, распознаваемого данным ДКА.
• объединение/пересечение языков, распознаваемых двумя данными ДКА.

Поскольку ДКА могут быть сведены к канонической форме (минимальных ДКА), есть также два эффективных алгоритма определения

• принимает ли ДКА какую-либо строку (Задача проверки пустоты)
• принимает ли ДКА все строки (Задача проверки универсальности)
• принимают ли два ДКА один и тот же язык (Задача проверки эквивалентности)
• содержится ли язык, распознаваемый ДКА, в язык, распознаваемый другим ДКА (Задача проверки включения)
• ДКА с минимальным числом состояний для конкретного регулярного языка (Задача минимизации)

ДКА эквивалентны по вычислительным возможностям недетерминированным конечным автоматам (НКА, англ. nondeterministic finite automata, NFAs). Это потому, во-первых, что любой ДКА является также и НКА, так что НКА может делать всё, что может делать ДКА. Также, если дан НКА, с помощью сведения ДКА к НКА^[англ.] можно построить ДКА, который распознаёт тот же самый язык, что и НКА, хотя ДКА может иметь экспоненциально большее число состояний, чем НКА^[11][12]. Однако даже при вычислительной эквивалентности НКА автоматам ДКА, вышеупомянутые задачи не обязательно решаются эффективно для НКА. Задача неуниверсальности для НКА имеет сложность PSPACE, поскольку имеются небольшие НКА с отклоняемыми наименьшими словами экспоненциального размера. ДКА является универсальным тогда и только тогда, когда все состояния являются конечными, но это неверно для НКА. Задачи эквивалентности, включения и минимизации также имеют сложность PSPACE, поскольку они требуют формирования дополнения НКА, что приводит к экспоненциальному взрыву размера^[13].

С другой стороны, конечные автоматы сильно ограничены в языках, которые они распознают. Много простых языков, включая любую задачу, требующую более чем постоянной памяти для решения, не могут быть распознаны ДКА. Классическим примером простого языка, который не может распознать никакой ДКА, являются скобки или язык Дика, то есть язык, который состоит из правильно расставленных скобок, как в слове «(()())». Интуитивно ясно, что никакой ДКА не может распознать язык Дика, поскольку ДКА не в состоянии делать подсчёты — подобным ДКА автоматам нужно состояние, представляющее любое возможное число «открытых» скобок, что означает, что нужно иметь неограниченное число состояний. Другим простым примером является язык, состоящий из строк вида ${\displaystyle a^{n}b^{n}}$ для некоторого конечного, но произвольно большого числа букв a с последующим равным числом букв b^[14].

См. также

• Детерминированный ациклический конечный автомат^[англ.]
• Минимизация ДКА
• Монадическая логика второго порядка^[англ.]
• Сведение НКА к ДКА^[англ.]
• Квантовый конечный автомат^[англ.]
• Машины Тьюринга с движущейся вправо читающей головкой^[англ.]
• Задача разделения слов^[англ.]
• Машина Тьюринга
• Двухсторонний детерминированный конечный автомат^[англ.]

Примечания

1. Hopcroft, Motwani, Ullman, 2001.
2. McCulloch, Pitts, 1943.
3. Rabin, Scott, 1959.
4. Hopcroft, Ullman, 1979, с. 59—60.
5. Lawson, 2004, с. 129.
6. Sakarovitch, 2009, с. 228.
7. Lawson, 2004, с. 128.
8. Грушо, 1973, с. 633–637.
9. Cai, Devroye, 2017, с. 428–458.
10. Carayol, Nicaud, 2012, с. 194–205.
11. Sakarovitch, 2009, с. 105.
12. Lawson, 2004, с. 63.
13. Startseite - Lehrstuhl für Theoretische Informatik  (неопр.). Дата обращения: 6 февраля 2020. Архивировано 8 августа 2018 года.
14. Lawson, 2004, с. 46.

Литература

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation. — 2. — Addison Wesley, 2001. — ISBN 0-201-44124-1.
• Mark V. Lawson. Finite automata. — Chapman and Hall/CRC, 2004. — ISBN 1-58488-255-7.
• McCulloch W. S., Pitts W. A Logical Calculus of the Ideas Immanent in Nervous Activity // Bulletin of Mathematical Biophysics. — 1943. — Т. 5, вып. 4. — С. 115–133. — doi:10.1007/BF02478259. Архивировано 12 апреля 2019 года.
• Rabin M. O., Scott D. Finite automata and their decision problems. // IBM J. Res. Dev. — 1959. — Т. 3, вып. 2. — С. 114–125. — doi:10.1147/rd.32.0114.
• Jacques Sakarovitch. Elements of automata theory / Translated from the French by Reuben Thomas. — Cambridge: Cambridge University Press, 2009. — ISBN 978-0-521-84425-3.
• Michael Sipser. Introduction to the Theory of Computation. — Boston: PWS, 1997. — ISBN 0-534-94728-X. Section 1.1: Finite Automata, pp. 31-47. Subsection «Decidable Problems Concerning Regular Languages» of section 4.1: Decidable Languages, pp. 152—155.4.4 DFA can accept only regular language
• John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. — Reading/MA: Addison-Wesley, 1979. — ISBN 0-201-02988-X.
  • Перевод Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. — Москва, Санкт-Петербург, Киев: Вильямс, 2002. — ISBN 5-8459-0261-4.
• Грушо А. А. О предельных распределениях некоторых характеристик случайных автоматных графов // Матем. заметки. — 1973. — Т. 4. — P. 133–141, 633–637. — doi:10.1007/BF01095785.
• Xing Shi Cai, Luc Devroye. The graph structure of a deterministic automaton chosen at random // Random Structures & Algorithms. — 2017. — Октябрь (т. 51, вып. 3). — doi:10.1002/rsa.20707.
• Arnaud Carayol, Cyril Nicaud. Distribution of the number of accessible states in a random deterministic automaton // STACS'12 (29th Symposium on Theoretical Aspects of Computer Science). — Paris, France, 2012. — Т. 14.