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

«DFSA» перенаправляется сюда. Этот термин может также относиться к сексуальному насилию с применением наркотиков .

Пример детерминированного конечного автомата, который принимает только двоичные числа, кратные 3. Состояние S ₀ является одновременно начальным и приемным состоянием. Например, строка «1001» ведет к последовательности состояний S0 _, S1 _, S2 _, S1 _, S0 _и , следовательно, принимается.

В теории вычислений , разделе теоретической информатики , детерминированный конечный автомат ( DFA ) — также известный как детерминированный конечный акцептор ( DFA ), детерминированный конечный автомат ( DFSM ) или детерминированный конечный автомат ( DFSA ) — — это конечный автомат , который принимает или отклоняет заданную строку символов, проходя последовательность состояний, однозначно определяемую этой строкой. Детерминированный означает уникальность выполнения вычислений. В поисках простейших моделей для описания конечных автоматов Уоррен Маккалок и Уолтер Питтс были одними из первых исследователей, представивших в 1943 году концепцию, подобную конечным автоматам.

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

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

DFA были обобщены на недетерминированные конечные автоматы (NFA) , которые могут иметь несколько стрелок с одной и той же меткой, начинающихся из состояния. Используя метод построения powerset , каждый NFA можно перевести в DFA, распознающий тот же язык. DFA, а также NFA распознают именно набор обычных языков .

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

Детерминированный конечный автомат M 5- ( представляет собой Q , Σ, δ , q0 _, кортеж F ) , состоящий из

• конечное множество состояний Q
• конечный набор входных символов, называемый алфавитом Σ
• перехода функция δ : Q × Σ → Q
• начальное или начальное состояние $q_{0}\in Q$
• набор состояний принятия $F\subseteq Q$

Пусть w = a ₁ a ₂ ... an _— строка в алфавите Σ . Автомат M принимает строку w, последовательность состояний r ₀ , r ₁ , ..., r _n существует если в Q со следующими условиями:

1. р ₀ = д ₀
2. r _{i +1} = δ ( r _i , a _{i +1} ) , for i = 0, ..., n − 1
3. $r_{n}\in F$.

На словах первое условие говорит о том, что машина запускается в стартовом состоянии q ₀ . Второе условие гласит, что с учетом каждого символа строки w машина будет переходить из состояния в состояние в соответствии с функцией перехода δ . Последнее условие говорит, что машина принимает w , если последний ввод w приводит к остановке машины в одном из состояний принятия. В противном случае говорят, что автомат отвергает строку. Набор строк, который M, принимает — это язык, распознаваемый M , и этот язык обозначается L ( M ) .

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

Более полное введение формального определения см. в теории автоматов .

Пример

Следующий пример представляет собой DFA M с двоичным алфавитом, который требует, чтобы входные данные содержали четное количество нулей.

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

M знак равно ( Q , Σ, δ , q ₀ , F ) где

• Q знак равно { S ₁ , S ₂ }
• Σ = {0, 1}
• q ₀ = S ₁
• F = { S ₁ } и
• δ определяется следующей таблицей переходов состояний :

	0	1
С 1	SS2	С 1
SS2	С 1	SS2

Состояние S1 _{означает ,} что на данный момент во входных данных было четное количество нулей, а состояние означает _S2 нечетное число. 1 на входе не меняет состояние автомата. Когда ввод закончится, состояние покажет, содержало ли вход четное количество нулей или нет. Если входные данные содержали четное количество нулей, M завершит работу в состоянии S ₁ , состоянии принятия, поэтому входная строка будет принята.

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

Вариации

Полные и неполные

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

Хотя это наиболее распространенное определение, некоторые авторы используют термин «детерминированный конечный автомат» для несколько другого понятия: автомат, который определяет не более одного перехода для каждого состояния и каждого входного символа; функция перехода может быть частичной . Если переход не определен, такой автомат останавливается.

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

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

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

Случайность

Когда начальное состояние и состояния принятия игнорируются, DFA из n состояний и алфавита размера k можно рассматривать как орграф из n вершин, в котором все вершины имеют k исходящих дуг, помеченных 1, ..., k ( ak -внешний диграф). Известно, что когда k ≥ 2 — фиксированное целое число, с большой вероятностью наибольшая сильно связная компонента (SCC) в таком равномерно выбранном наугад k -out орграфе имеет линейный размер и достижима всеми вершинами. Также было доказано, что если k разрешено увеличиваться с увеличением n , то весь орграф имеет фазовый переход для сильной связности, аналогичный модели Эрдеша – Реньи для связности.

В случайном DFA максимальное количество вершин, достижимых из одной вершины, с высокой вероятностью очень близко к количеству вершин в наибольшем SCC . Это также верно для наибольшего индуцированного подграфа минимальной степени, который можно рассматривать как направленную версию 1 -core .

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

Верхний левый автомат распознает язык всех двоичных строк, содержащих хотя бы одно вхождение «00». Правый нижний автомат распознает все двоичные строки с четным номером «1». Левый нижний автомат получается как произведение первых двух, он распознает пересечение обоих языков.

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

• Союз
• Пересечение (см. картинку)
• Конкатенация
• Дополнить
• Закрытие Клини
• Разворот
• частное
• Замена
• Гомоморфизм

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

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

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

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

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

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

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

${\widehat {\delta }}$ определено для всех слов $w\in \Sigma ^{*}$. Прогон DFA представляет собой последовательность композиций ${\widehat {\delta }}$ с самим собой.

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

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

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

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

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

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

DFA эквивалентны по вычислительной мощности недетерминированным конечным автоматам (NFA). Это связано с тем, что, во-первых, любой DFA также является NFA, поэтому NFA может делать то же, что и DFA. Кроме того, учитывая NFA, используя конструкцию powerset, можно построить DFA, который распознает тот же язык, что и NFA, хотя DFA может иметь экспоненциально большее количество состояний, чем NFA. Однако, несмотря на то, что NFA вычислительно эквивалентны DFA, вышеупомянутые проблемы не обязательно решаются эффективно и для NFA. Проблема неуниверсальности NFA является PSPACE-полной , поскольку существуют небольшие NFA с кратчайшим отклоняющим словом экспоненциального размера. DFA является универсальным тогда и только тогда, когда все состояния являются конечными состояниями, но это не относится к NFA. Проблемы равенства, включения и минимизации также являются PSPACE полными, поскольку они требуют формирования дополнения к NFA, что приводит к экспоненциальному увеличению размера.

С другой стороны, автоматы с конечным числом состояний имеют строго ограниченную мощность на языках, которые они могут распознавать; многие простые языки, включая любую проблему, для решения которой требуется больше, чем постоянное пространство, не могут быть распознаны DFA. Классическим примером просто описанного языка, который не может распознать ни один DFA, является скобочный язык или язык Дика , т. е. язык, который состоит из правильно парных скобок, таких как слово «(()())». Интуитивно понятно, что ни один DFA не может распознать язык Дейка, потому что DFA не способен считать: автомату, подобному DFA, необходимо иметь состояние для представления любого возможного количества «открытых в данный момент» круглых скобок, а это означает, что ему потребуется неограниченное количество состояний. Другой более простой пример — язык, состоящий из строк вида a ^н б ^н но произвольного числа a для некоторого конечного , количество b , за которым следует такое же .

Идентификация DFA по помеченным словам

Основная статья: Индукция регулярных языков

Дан набор позитивных слов $S^{+}\subset \Sigma ^{*}$ и набор негативных слов $S^{-}\subset \Sigma ^{*}$ можно построить ДКА, который принимает все слова из $S^{+}$ и отвергает все слова из $S^{-}$: эта проблема называется DFA-идентификация (синтез, обучение).Хотя некоторые ДКА могут быть построены за линейное время, проблема идентификации ДКА с минимальным числом состояний является NP-полной. Первый алгоритм минимальной идентификации DFA был предложен Трахтенбротом и Барздином. и называется ТБ-алгоритмом .Однако TB-алгоритм предполагает, что все слова из $\Sigma$ до заданной длины содержатся либо в $S^{+}\cup S^{-}$.

Позднее К. Ланг предложил расширение ТБ-алгоритма, не использующее никаких предположений о $S^{+}$ и $S^{-}$, алгоритм Traxbar . Однако Traxbar не гарантирует минимальность построенного DFA.В своей работе EM Gold также предложил эвристический алгоритм для минимальной идентификации DFA.Алгоритм Голда предполагает, что $S^{+}$ и $S^{-}$ содержать характерный набор регулярного языка; в противном случае построенный DFA будет несовместим либо с $S^{+}$ или $S^{-}$.Другие известные алгоритмы идентификации DFA включают алгоритм RPNI, основанный на доказательствах алгоритм объединения состояний Blue-Fringe, и оконный-EDSM. Еще одним направлением исследований является применение эволюционных алгоритмов : эволюционный алгоритм интеллектуальной маркировки состояний. позволило решить модифицированную задачу идентификации DFA, в которой обучающие данные (наборы $S^{+}$ и $S^{-}$) зашумлен в том смысле, что некоторые слова относятся к неправильным классам.

Еще один шаг вперед был сделан благодаря использованию SAT решателей Марджином Дж. Хойле и С. Вервером: минимальная задача идентификации DFA сведена к определению выполнимости булевой формулы. Основная идея состоит в том, чтобы построить акцептор расширенного префиксного дерева ( дерево, содержащее все входные слова с соответствующими метками) на основе входных наборов и уменьшить проблему поиска DFA с $C$ указывает на раскраску вершин дерева с помощью $C$ состояния таким образом, что при объединении вершин одного цвета в одно состояние сгенерированный автомат является детерминированным и соответствует $S^{+}$ и $S^{-}$.Хотя этот подход позволяет найти минимальный DFA, он страдает от экспоненциального увеличения времени выполнения при увеличении размера входных данных.Поэтому первоначальный алгоритм Хойле и Вервера позже был дополнен выполнением нескольких шагов алгоритма EDSM перед выполнением решателя SAT: алгоритма DFASAT. Это позволяет сократить пространство поиска задачи, но приводит к потере гарантии минимальности.Другой способ сокращения пространства поиска был предложен Ульянцевым и др. с помощью новых предикатов нарушения симметрии, основанных на алгоритме поиска в ширину :искомые состояния DFA ограничены нумерацией в соответствии с алгоритмом BFS, запускаемым из исходного состояния. Этот подход уменьшает пространство поиска на $C!$ путем исключения изоморфных автоматов.

Эквивалентные модели

Правосторонние машины Тьюринга

Машины Тьюринга, движущиеся вправо только для чтения, представляют собой особый тип машины Тьюринга , которая движется только вправо; этипочти точно эквивалентны DFA. Определение, основанное на единственной бесконечной ленте, представляет собой семикортеж

$M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,$

где

$Q$ — конечное множество состояний ;

$\Gamma$ — конечное множество ленточных алфавитов/символов ;

$b\in \Gamma$ — пустой символ (единственный символ, который может появляться на ленте бесконечно часто на любом этапе вычислений);

$\Sigma$, подмножество $\Gamma$ не включая b , — набор входных символов ;

$\delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}$ – функция, называемая функцией перехода , R – движение вправо (сдвиг вправо);

$q_{0}\in Q$ — исходное состояние ;

$F\subseteq Q$ — это набор конечных или принимающих состояний .

Машина всегда принимает обычный язык. Должен существовать хотя бы один элемент множества F ( состояние HALT ), чтобы язык был непустым.

машины Тьюринга с 3 состояниями и 2 символами, доступной только для

	Текущее состояние А			Текущее состояние Б			Текущее состояние C
символ ленты	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние	Написать символ	Переместить ленту	Следующее состояние
0	1	Р	Б	1	Р	А	1	Р	Б
1	1	Р	С	1	Р	Б	1	Н	ОСТАНОВКА

$Q=\{A,B,C,{\text{HALT}}\};$

$\Gamma =\{0,1\};$

$b=0$, "пустой";

$\Sigma =\varnothing$, пустой набор;

$\delta =$ см. таблицу состояний выше;

$q_{0}=A$, исходное состояние;

$F=$ одноэлементный набор конечных состояний: $\{{\text{HALT}}\}$.

См. также

• Детерминированный ациклический конечный автомат
• Минимизация DFA
• Монадическая логика второго порядка
• Конструкция Powerset
• Квантовый конечный автомат
• Проблема с разделением слов
• Машина Тьюринга
• Двусторонний конечный автомат
• Взвешенный автомат

Ссылки

• Хопкрофт, Джон Э .; Мотвани, Раджив ; Уллман, Джеффри Д. (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Бостон: Эддисон Уэсли . ISBN  0-201-44124-1 .
• Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл/CRC. ISBN  1-58488-255-7 . Збл   1086.68074 .
• Маккалок, штат Вашингтон; Питтс, В. (1943). «Логическое исчисление идей, имманентных нервной деятельности». Вестник математической биофизики . 5 (4): 115–133. дои : 10.1007/BF02478259 . ПМИД   2185863 .
• Рабин, Миссури; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения» . IBM J. Res. Дев . 3 (2): 114–125. дои : 10.1147/рд.32.0114 .
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-84425-3 . Збл   1188.68177 .
• Сипсер, Майкл (1997). Введение в теорию вычислений . Бостон: PWS. ISBN  0-534-94728-Х . . Раздел 1.1: Конечные автоматы, стр. 31–47. Подраздел «Разрешимые проблемы, касающиеся регулярных языков» раздела 4.1: Разрешимые языки, стр. 152–155.4.4 DFA может принимать только обычный язык.