Детерминированный конечный автомат - Deterministic finite automaton

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

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

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

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

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

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

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

конечный набор состояний $Q$
конечный набор входных символов, называемый алфавитом $Σ$
функция перехода $δ : Q \times Σ \to Q$
начальное или начальное состояние ${\ displaystyle q_ {0} \ in Q}$
набор состояний принятия ${\ Displaystyle F \ substeq Q}$

Пусть $w = a 1 a 2 \dots a n$ - строка в алфавите $Σ$ . Автомат $M$ принимает строку $w,$ если последовательность состояний $r 0, r 1,\dots, r n$ существует в $Q$ со следующими условиями:

$г 0 = q 0$
$r i +1 = δ (r i, a i +1)$ , для $i = 0,\dots, n - 1$
${\ displaystyle r_ {n} \ in F}$ .

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

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

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

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

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

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

Пример

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

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

$M = (Q, Σ, δ, q 0, F),$ где

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

	0	1
S ₁	S ₂	S ₁
S ₂	S ₁	S ₂

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

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

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

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

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

Союз
Пересечение (см. Рисунок)
Конкатенация
Отрицание
Клини закрытие
Разворот
В этом
Частное
Замена
Гомоморфизм

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

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

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

Для данного входного символа можно построить функцию перехода , определив для всех . (Этот трюк называется каррированием .) С этой точки зрения, «воздействует» на состояние в Q, создавая другое состояние. Затем можно рассмотреть результат функции композиции неоднократно обращался к различным функциям , и так далее. Имея пару букв , можно определить новую функцию , где обозначает композицию функции. ${\ displaystyle a \ in \ Sigma}$ ${\ displaystyle \ delta _ {a}: Q \ rightarrow Q}$ ${\ Displaystyle \ дельта _ {а} (д) = \ дельта (д, а)}$ ${\ displaystyle q \ in Q}$ ${\ displaystyle \ delta _ {a}}$ ${\ 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}}}$ определяется для всех слов . Запуск DFA - это последовательность композиций с самим собой. ${\ Displaystyle ш \ в \ Sigma ^ {*}}$ ${\ displaystyle {\ widehat {\ delta}}}$

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

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

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

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

Случайный

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

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

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

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

дополнение языка, распознаваемого данным 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 ⁿ b ⁿ для некоторого конечного, но произвольного числа a , за которым следует такое же количество b .

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

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

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

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

Languages

In other projects