В теории вычислений , раздел теоретической информатики , детерминированный конечный автомат ( DFA ) - также известный как детерминированный конечный акцептор ( DFA ), детерминированный конечный автомат ( DFSM ) или детерминированный конечный автомат ( DFSA ) - - это конечный автомат, который принимает или отклоняет заданную строку символов, проходя через последовательность состояний, однозначно определяемую строкой. [1] Детерминированныйотносится к уникальности выполнения вычислений. В поисках простейших моделей для захвата конечных автоматов Уоррен МакКаллох и Уолтер Питтс были одними из первых исследователей, которые в 1943 году представили концепцию, аналогичную конечным автоматам [2] [3].
На рисунке показан детерминированный конечный автомат с использованием диаграммы состояний . В этом примере автомата есть три состояния: S 0 , S 1 и S 2 (обозначены графически кружками). Автомат принимает на вход конечную последовательность нулей и единиц. Для каждого состояния есть стрелка перехода, ведущая к следующему состоянию как для 0, так и для 1. После считывания символа DFA детерминированно переходит из одного состояния в другое, следуя стрелке перехода. Например, если автомат в настоящее время находится в состоянии S 0, а текущий входной символ равен 1, то он детерминированно переходит в состояние S 1 . DFA имеет начальное состояние (обозначенное стрелкой, идущей из ниоткуда), где начинаются вычисления, и набор состояний принятия (обозначенных графически двойным кружком), которые помогают определить, когда вычисление было успешным.
DFA определяется как абстрактная математическая концепция, но часто реализуется в аппаратном и программном обеспечении для решения различных конкретных задач, таких как лексический анализ и сопоставление с образцом . Например, DFA может моделировать программное обеспечение, которое решает, являются ли вводимые пользователем данные, такие как адреса электронной почты, синтаксически допустимыми. [4]
DFA были обобщены на недетерминированные конечные автоматы (NFA), которые могут иметь несколько стрелок с одной и той же меткой, начиная с состояния. Используя метод построения powerset , каждую NFA можно перевести в DFA, который распознает тот же язык. DFA и NFA точно распознают набор обычных языков . [1]
Формальное определение
Детерминированный конечный автомат М представляет собой 5- кортеж , ( Q , Σ, δ , д 0 , F ) , состоящий из
- конечный набор состояний Q
- конечный набор входных символов, называемый алфавитом Σ
- функция перехода δ : Q × Σ → Q
- начальное или начальное состояние
- набор состояний принятия
Пусть w = a 1 a 2 … a n - строка в алфавите Σ . Автомат M принимает строку w, если последовательность состояний r 0 , r 1 ,…, r n существует в Q со следующими условиями:
- г 0 = q 0
- r i +1 = δ ( r i , a i +1 ) , для i = 0,…, n - 1
- .
На словах первое условие говорит о том, что машина запускается в стартовом состоянии q 0 . Второе условие говорит, что для каждого символа строки w автомат будет переходить из состояния в состояние в соответствии с функцией перехода δ . Последнее условие говорит, что машина принимает w, если последний ввод w заставляет машину останавливаться в одном из состояний приема. В противном случае говорят, что автомат отклоняет строку. Набор строк, M , принимает это язык признан на М и этот язык обозначается L ( M ) .
Детерминированный конечный автомат без принимающих состояний и без начального состояния известен как переходная система или полуавтомат .
Для более полного введения формального определения см. Теорию автоматов .
Полное и неполное
Согласно приведенному выше определению детерминированные конечные автоматы всегда полны : они определяют переход для каждого состояния и каждого входного символа.
Хотя это наиболее распространенное определение, некоторые авторы используют термин детерминированный конечный автомат для немного другого понятия: автомат, который определяет не более одного перехода для каждого состояния и каждого входного символа; функция перехода может быть частичной . [5] Если переход не определен, такой автомат останавливается.
Пример
Следующий пример представляет собой DFA M с двоичным алфавитом, который требует, чтобы вход содержал четное количество нулей.
M = ( Q , Σ, δ , q 0 , F ), где
- Q = { S 1 , S 2 }
- Σ = {0, 1}
- q 0 = S 1
- F = { S 1 } и
- δ определяется следующей таблицей переходов состояний :
0 1 S 1 S 2 S 1 S 2 S 1 S 2
Состояние S 1 означает, что до сих пор на входе было четное количество нулей, а S 2 означает нечетное число. 1 на входе не меняет состояние автомата. Когда ввод закончится, состояние покажет, содержал ли ввод четное число нулей или нет. Если вход содержал четное количество нулей, M завершит работу в состоянии S 1 , состоянии приема, поэтому входная строка будет принята.
Язык, распознаваемый M, является регулярным языком, задаваемым регулярным выражением (1*) (0 (1*) 0 (1*))*
, где *
- звезда Клини , например, 1*
обозначает любое количество (возможно, ноль) следующих друг за другом единиц.
Свойства закрытия
Если DFA распознают языки, полученные в результате применения операции к распознаваемым DFA языкам, то говорят, что DFA закрыты при выполнении операции. DFA закрываются при следующих операциях.
- Союз
- Пересечение [6] : 59–60 (см. Рисунок)
- Конкатенация
- Отрицание
- Клини закрытие
- Разворот
- В этом
- Quotient [ необходима цитата ]
- Замена [ необходима ссылка ]
- Гомоморфизм [ необходима ссылка ]
Для каждой операции в исследовании сложности состояний была определена оптимальная конструкция по количеству состояний . Так как ДКА являются эквивалентом для недетерминированных конечных автоматов (НКА), эти укупорочные средства также могут быть доказаны с помощью закрывающих свойств НКА.
Как переходный моноид
Прогон данного DFA можно рассматривать как последовательность составов очень общей формулировки переходной функции с самим собой. Здесь мы строим эту функцию.
Для заданного входного символа , можно построить переходную функцию определяя для всех . (Этот трюк называется каррированием .) С этой точки зрения,«действует» на состояние в Q, чтобы создать другое состояние. Затем можно рассмотреть результат композиции функций, многократно применяемой к различным функциям., , и так далее. Учитывая пару букв, можно определить новую функцию , где обозначает композицию функций.
Ясно, что этот процесс можно рекурсивно продолжить, дав следующее рекурсивное определение :
- , где это пустая строка и
- , где а также .
определено для всех слов . Запуск DFA - это последовательность составов с собой.
Повторяющаяся функциональная композиция образует моноид . Для функций перехода этот моноид известен как моноид перехода или иногда полугруппа преобразований . Конструкция также может быть обратной: с учетом, можно восстановить , поэтому два описания эквивалентны.
Локальные автоматы
Локальный автомат является, не обязательно является полным, DFA , для которого все ребра с одной и той же этикетки приводят к одной вершине. Локальные автоматы принимают класс локальных языков , для которых принадлежность слова к языку определяется «скользящим окном» длины два на слове. [7] [8]
Myhill график в алфавите A представляет собой ориентированный граф с множеством вершин A и подмножеств вершин помеченных «старт» и «Завершить». Язык, принятый графом Майхилла, - это набор ориентированных путей от начальной вершины к конечной вершине: таким образом, граф действует как автомат. [7] Класс языков, принятый графами Майхилла, - это класс местных языков. [9]
Случайный
Когда начальное состояние и состояния принятия игнорируются, DFA из n состояний и алфавита размера k можно рассматривать как орграф из n вершин, в котором все вершины имеют k выходных дуг, обозначенных 1, ..., k ( k- выход орграф). Известно, что когда k ≥ 2 - фиксированное целое число, с большой вероятностью самая большая сильно связная компонента (SCC) в таком k- выходном орграфе, выбранном равномерно случайным образом, имеет линейный размер и может быть достигнута всеми вершинами. [10] Также было доказано, что если разрешено увеличивать k с увеличением n , то весь орграф имеет фазовый переход для сильной связности, аналогичный модели Эрдеша – Реньи для связности. [11]
В случайном DFA максимальное количество вершин, достижимых из одной вершины, с большой вероятностью очень близко к количеству вершин в самом большом SCC . [10] [12] Это также верно для самого большого индуцированного суб-орграфа с минимальной внутренней степенью, который можно рассматривать как направленную версию 1- ядра . [11]
Преимущества и недостатки
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. [13] [14] Однако, хотя NFA в вычислительном отношении эквивалентны DFA, вышеупомянутые проблемы не обязательно эффективно решаются также и для NFA. Проблема неуниверсальности для NFA является полной PSPACE, поскольку есть небольшие NFA с кратчайшим отклоняющим словом экспоненциального размера. DFA универсален тогда и только тогда, когда все состояния являются конечными, но это не верно для NFA. Задачи равенства, включения и минимизации также являются завершенными для PSPACE, поскольку они требуют формирования дополнения к NFA, что приводит к экспоненциальному увеличению размера. [15]
С другой стороны, конечные автоматы имеют строго ограниченную мощность на языках, которые они могут распознать; многие простые языки, включая любую проблему, для решения которой требуется больше, чем постоянное пространство, не распознаются DFA. Классическим примером просто описанного языка, который не может распознать DFA, является язык скобок или язык Дайка , то есть язык, который состоит из правильно парных скобок, таких как слово «(() ())». Интуитивно понятно, что ни один DFA не может распознать язык Дайка, потому что DFA не способны считать: DFA-подобный автомат должен иметь состояние, представляющее любое возможное количество «открытых в данный момент» круглых скобок, что означает, что ему потребуется неограниченное количество состояний. Другой более простой пример - это язык, состоящий из строк вида a n b n для некоторого конечного, но произвольного числа a , за которым следует такое же количество b . [16]
Идентификация DFA по помеченным словам
Учитывая набор положительных слови набор отрицательных слов можно построить DFA, который принимает все слова из и отвергает все слова из : эта проблема называется идентификацией DFA (синтез, обучение). Хотя некоторые DFA могут быть построены за линейное время, проблема идентификации DFA с минимальным числом состояний является NP-полной. [17] Первый алгоритм минимальной идентификации DFA был предложен Трахтенбротом и Барздиным в [18] и называется TB-алгоритмом . Однако TB-алгоритм предполагает, что все слова из до заданной длины содержатся либо в .
Позже К. Ланг предложил расширение TB-алгоритма, не использующее никаких предположений о а также Traxbar алгоритм. [19] Однако Traxbar не гарантирует минимальность построенного DFA. В своей работе [17] Э.М. Голд также предложил эвристический алгоритм для минимальной идентификации DFA. Алгоритм Голда предполагает, что а также содержат характеристический набор регулярного языка; в противном случае построенный DFA будет несовместим ни с или же . Другие известные алгоритмы идентификации DFA включают алгоритм RPNI, [20] алгоритм слияния состояний, основанный на доказательствах Blue-Fringe, [21] Windowed-EDSM. [22] Еще одним направлением исследований является применение эволюционных алгоритмов : эволюционный алгоритм маркировки интеллектуального состояния [23] позволил решить модифицированную задачу идентификации DFA, в которой обучающие данные (наборы а также ) шумно в том смысле, что некоторые слова отнесены к неправильным классам.
Еще один шаг вперед связан с применением SAT- решателей Marjin J..H. Heule и S. Verwer: задача минимальной идентификации DFA сводится к определению выполнимости булевой формулы. [24] Основная идея заключается в том, чтобы построить дополненной префикс-дерево акцептора (а TRIE , содержащий все входные слова с соответствующими этикетками) на основе входных наборов и уменьшить проблему нахождения DFA ссостояний раскрасить вершины дерева в состояний таким образом, что когда вершины с одним цветом объединяются в одно состояние, сгенерированный автомат является детерминированным и соответствует а также . Хотя этот подход позволяет найти минимальный DFA, он страдает от экспоненциального увеличения времени выполнения при увеличении размера входных данных. Поэтому первоначальный алгоритм Хёля и Вервера был позже дополнен несколькими шагами алгоритма EDSM перед выполнением решателя SAT: алгоритмом DFASAT. [25] Это позволяет сократить пространство поиска задачи, но приводит к потере гарантии минимальности. Другой способ сокращения пространства поиска был предложен в [26] с помощью новых предикатов нарушения симметрии, основанных на алгоритме поиска в ширину : искомые состояния DFA ограничены, чтобы быть пронумерованными в соответствии с алгоритмом BFS, запущенным из начального состояния. Такой подход сокращает пространство поиска на устранением изоморфных автоматов.
Смотрите также
- Ациклические детерминированные конечные автоматы
- Минимизация DFA
- Монадическая логика второго порядка
- Преобразование NFA в DFA
- Квантовые конечные автоматы
- Право движущиеся машины Тьюринга только для чтения
- Проблема разделения слов
- Машина Тьюринга
- Двусторонний детерминированный конечный автомат
Заметки
- ^ a b Хопкрофт 2001 :
- ^ Маккалок и Питтс (1943) :
- ^ Рабин и Скотт (1959) :
- ^ Гауда, Прабхакар, Применение конечных автоматов
- ^ Могенсен, Торбен Эгидиус (2011). «Лексический анализ». Введение в проектирование компилятора . Бакалавриат по информатике. Лондон: Спрингер. п. 12. DOI : 10.1007 / 978-0-85729-829-4_1 . ISBN 978-0-85729-828-7.
- ^ Джон Э. Хопкрофт и Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг / МА: Аддисон-Уэсли. ISBN 0-201-02988-X.
- ^ а б Лоусон (2004) стр.129
- ^ Sakarovitch (2009) с.228
- ^ Лоусон (2004) стр.128
- ^ а б Грушо, А.А. (1973). «Предельные распределения некоторых характеристик графов случайных автоматов». Математические заметки АН СССР . 4 : 633–637. DOI : 10.1007 / BF01095785 . S2CID 121723743 .
- ^ а б Цай, Син Ши; Деврой, Люк (октябрь 2017 г.). «Структура графа детерминированного автомата, выбранного случайным образом». Случайные структуры и алгоритмы . 51 (3): 428–458. arXiv : 1504.06238 . DOI : 10.1002 / rsa.20707 . S2CID 13013344 .
- ^ Карайоль, Арно; Никауд, Кирилл (февраль 2012 г.). Распределение количества доступных состояний в случайном детерминированном автомате . STACS'12 (29-й симпозиум по теоретическим аспектам информатики). 14 . Париж, Франция. С. 194–205.
- ^ Sakarovitch (2009) стр.105
- ^ Lawson (2004) стр.63
- ^ https://www7.in.tum.de/um/courses/auto/ws1718/slides1718/04-Implementations_sets.pdf
- ↑ Лоусон (2004), стр.46
- ^ а б Золото, EM (1978). «Сложность идентификации автоматов по заданным данным» . Информация и контроль . 37 (3): 302–320. DOI : 10.1016 / S0019-9958 (78) 90562-4 .
- ^ Де Врис, А. (28 июня 2014 г.). Конечные автоматы: поведение и синтез . ISBN 9781483297293.
- ^ Ланг, Кевин Дж. (1992). «Случайные DFA можно приблизительно узнать из редких унифицированных примеров». Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92 . С. 45–52. DOI : 10.1145 / 130385.130390 . ISBN 089791497X. S2CID 7480497 .
- ^ Oncina, J .; Гарсия, П. (1992). «Вывод регулярных языков в полиномиальное обновленное время». Распознавание образов и анализ изображений . Серия по машинному восприятию и искусственному интеллекту. 1 . С. 49–61. DOI : 10.1142 / 9789812797902_0004 . ISBN 978-981-02-0881-3.
- ^ Ланг, Кевин Дж .; Перлмуттер, Барак А .; Прайс, Родни А. (1998). «Результаты конкурса Abbadingo one DFA по обучению и новый алгоритм слияния состояний, основанный на доказательствах». Грамматический вывод (PDF) . Конспект лекций по информатике. 1433 . С. 1–12. DOI : 10.1007 / BFb0054059 . ISBN 978-3-540-64776-8.
- ^ "Beyond EDSM | Труды 6-го Международного коллоквиума по грамматическому выводу: алгоритмы и приложения" .
- ^ Лукас, С. М.; Рейнольдс, Т.Дж. (2005). «Изучение детерминированных конечных автоматов с помощью интеллектуального эволюционного алгоритма маркировки состояний». IEEE Transactions по анализу шаблонов и машинному анализу . 27 (7): 1063–1074. DOI : 10.1109 / TPAMI.2005.143 . PMID 16013754 . S2CID 14062047 .
- ^ Heule, MJH (2010). Точная идентификация DFA с помощью решателей SAT . Грамматический вывод: теоретические результаты и приложения. ICGI 2010. Конспект лекций по информатике. 6339 . С. 66–79. DOI : 10.1007 / 978-3-642-15488-1_7 .
- ^ Heule, Marijn JH ; Вервер, Сикко (2013). «Синтез программной модели с использованием решателей выполнимости». Эмпирическая программная инженерия . 18 (4): 825–856. DOI : 10.1007 / s10664-012-9222-Z . hdl : 2066/103766 . S2CID 17865020 .
- ^ Ульянцев Владимир; Закирзянов Илья; Шалыто, Анатолий (2015). "Основанные на BFS предикаты нарушения симметрии для идентификации DFA". Язык и теория автоматов и приложения . Конспект лекций по информатике. 8977 . С. 611–622. DOI : 10.1007 / 978-3-319-15579-1_48 . ISBN 978-3-319-15578-4.
Рекомендации
- Хопкрофт, Джон Э .; Мотвани, Раджив ; Ульман, Джеффри Д. (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон Уэсли . ISBN 0-201-44124-1. Проверено 19 ноября 2012 года .
- Лоусон, Марк В. (2004). Конечные автоматы . Чепмен и Холл / CRC. ISBN 1-58488-255-7. Zbl 1086.68074 .
- Маккаллох, WS; Питтс, В. (1943). «Логический расчет идей, присущих нервной деятельности». Вестник математической биофизики . 5 (4): 115–133. DOI : 10.1007 / BF02478259 . PMID 2185863 .
- Рабин, Миссури; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения» . IBM J. Res. Dev . 3 (2): 114–125. DOI : 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 может принимать только обычный язык.