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

Детерминированный конечный автомат ${\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». Нижний левый автомат получается как производный из первых двух, он распознаёт пересечение обоих языков.

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

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

Поскольку ДКА эквивалентны недетерминированным конечным автоматам (НКА, англ. 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 _{a}({\widehat {\delta }}(q,w))}$, где ${\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].

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

• 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.