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

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

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

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

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

DFA были обобщены на недетерминированные конечные автоматы (NFA) который может иметь несколько стрелок с одинаковой меткой, начиная с состояния. С использованием конструкция электростанции , каждый NFA может быть переведен в DFA, который распознает тот же язык. DFA, как и NFA, точно распознают набор обычные языки.^[1]

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

Детерминированный конечный автомат ${ 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 substeq Q}$

Позволять ${ Displaystyle ш = а_ {1} а_ {2} ... а_ {п}}$ быть строкой в ​​алфавите ${ displaystyle Sigma}$. Автомат ${ displaystyle M}$ принимает строку ${ displaystyle w}$ если последовательность состояний, ${ displaystyle r_ {0}, r_ {1}, ..., r_ {n}}$, существует в ${ displaystyle Q}$ со следующими условиями:

1. ${ displaystyle r_ {0} = q_ {0}}$
2. ${ Displaystyle г_ {я + 1} = дельта (г_ {я}, а_ {я + 1})}$, для ${ Displaystyle я = 0, ..., п-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)}$.

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

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

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

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

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

пример

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

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

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

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

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

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

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

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

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

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

Случайный

Когда начальное состояние и состояния принятия игнорируются, DFA ${ displaystyle n}$ состояния и алфавит размера ${ displaystyle k}$ можно рассматривать как диграф из ${ displaystyle n}$ вершины, в которых все вершины имеют ${ displaystyle k}$ маркированные дуги ${ displaystyle 1, ldots, k}$ (а ${ displaystyle k}$-из орграфа). Известно, что когда ${ Displaystyle к geq 2}$ - фиксированное целое число, с большой вероятностью наибольшее компонент сильной связности (SCC) в таком ${ displaystyle k}$-выходный орграф, выбранный равномерно случайным образом, имеет линейный размер и доступен для всех вершин.^[10] Также было доказано, что если ${ displaystyle k}$ разрешено увеличивать как ${ displaystyle n}$ увеличивается, то весь орграф имеет фазовый переход для сильной связности, аналогичный Модель Эрдеша – Реньи для подключения.^[11]

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

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

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

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

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

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

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

С другой стороны, конечные автоматы имеют строго ограниченную мощность на языках, которые они могут распознать; многие простые языки, включая любые проблемы, для решения которых требуется больше, чем постоянное пространство, не могут быть распознаны DFA. Классический пример просто описанного языка, который не может распознать DFA, - это скобки или Язык Дайка, т.е. язык, состоящий из правильно парных скобок, таких как слово "(() ())". Интуитивно понятно, что ни один DFA не может распознать язык Дайка, потому что DFA не умеют считать: DFA-подобный автомат должен иметь состояние, представляющее любое возможное количество «открытых в данный момент» круглых скобок, что означает, что ему потребуется неограниченное количество состояний. Другой более простой пример - это язык, состоящий из строк вида а^пб^п для некоторого конечного, но произвольного числа а's, за которым следует равное количество бс.^[16]

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

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

Позже К. Ланг предложил расширение TB-алгоритма, не использующее никаких предположений о ${ Displaystyle S ^ {+}}$ и ${ Displaystyle S ^ {-}}$ то Traxbar алгоритм.^[19]Однако Traxbar не гарантирует минимальность построенного DFA.^[17] Э. М. Голд также предложил эвристический алгоритм для минимальной идентификации DFA. Алгоритм Голда предполагает, что ${ Displaystyle S ^ {+}}$ и ${ Displaystyle S ^ {-}}$ содержать набор характеристик регулярного языка; в противном случае построенный DFA будет несовместим ни с ${ Displaystyle S ^ {+}}$ или ${ Displaystyle S ^ {-}}$. Другие известные алгоритмы идентификации DFA включают алгоритм RPNI,^[20] алгоритм слияния состояний, основанный на доказательствах Blue-Fringe,^[21] Оконный-ЭДСМ.^[22]Еще одно направление исследований - применение эволюционные алгоритмы: эволюционный алгоритм маркировки интеллектуального состояния^[23] позволили решить модифицированную задачу идентификации DFA, в которой обучающие данные (наборы ${ Displaystyle S ^ {+}}$ и ${ Displaystyle S ^ {-}}$) является шумный в том смысле, что некоторые слова относятся к неправильным классам.

Еще один шаг вперед связан с применением СИДЕЛ решатели M.J.H. Heule и S. Verwer: задача минимальной идентификации DFA сводится к определению выполнимости булевой формулы.^[24] Основная идея - построить расширенный акцептор префиксного дерева ( три содержащие все входные слова с соответствующими метками) на основе входных наборов и уменьшают проблему поиска DFA с ${ displaystyle C}$ заявляет раскраска вершины дерева с ${ displaystyle C}$ состояний таким образом, что когда вершины с одним цветом объединяются в одно состояние, сгенерированный автомат является детерминированным и соответствует ${ Displaystyle S ^ {+}}$ и ${ Displaystyle S ^ {-}}$Несмотря на то, что этот подход позволяет найти минимальный DFA, он страдает от экспоненциального увеличения времени выполнения при увеличении размера входных данных. Поэтому первоначальный алгоритм Heule и Verwer был позже расширен за счет выполнения нескольких шагов алгоритма EDSM до SAT. выполнение решателя: алгоритм DFASAT.^[25]Это позволяет сократить пространство поиска задачи, но ведет к потере гарантии минимальности. Другой способ сокращения пространства поиска был предложен в^[26] с помощью новых предикатов нарушения симметрии, основанных на поиск в ширину алгоритм: искомые состояния DFA ограничены для нумерации в соответствии с алгоритмом BFS, запущенным из начального состояния. Такой подход уменьшает пространство поиска на ${ displaystyle C!}$ устранением изоморфных автоматов.

Смотрите также

Заметки

использованная литература

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