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

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

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

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

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

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

Формальное определение [ править ]

Детерминированный конечный автомат $М$ представляет собой 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$ заставляет машину останавливаться в одном из состояний приема. В противном случае говорят, что автомат отклоняет строку. Набор строк, $М$ , принимает это язык признается на $М$ и этот язык обозначается через $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 ₁	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 закрываются при следующих операциях.

Союз
Пересечение ^[6]^{: 59–60} (см. Рисунок)
Конкатенация
Отрицание
Клини закрытие
Разворот
В этом
Quotient ^{[ необходима ссылка ]}
Замена ^{[ необходима ссылка ]}
Гомоморфизм ^{[ необходима ссылка ]}

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

Как переходный моноид [ править ]

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

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

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

Локальные автоматы [ править ]

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

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

Случайно [ править ]

Когда начальное состояние и состояния принятия игнорируются, DFA из $n$ состояний и алфавита размера $k$ можно рассматривать как орграф из $n$ вершин, в котором все вершины имеют $k$ выходных дуг, помеченных $1, ..., k$ ( $k-$ выход орграф). Известно, что когда $k \geq 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 ⁿ b ⁿдля некоторого конечного, но произвольного числа a , за которым следует такое же количество b . ^[16]

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

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

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

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

См. Также [ править ]

Ациклические детерминированные конечные автоматы
Минимизация 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
^ а б Грушо, AA (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
^ a b Голд, EM (1978). «Сложность идентификации автоматов по заданным данным» . Информация и контроль . 37 (3): 302–320. DOI : 10.1016 / S0019-9958 (78) 90562-4 .
↑ De Vries, A. (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.
^ «За пределами EDSM | Труды 6-го Международного коллоквиума по грамматическому выводу: алгоритмы и приложения» .
^ Лукас, SM; Рейнольдс, Т.Дж. (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 . ЛВП : 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 может принимать только обычный язык.

[Hopcroft_2001-1] Хопкрофт 2001 :

[2] Маккаллох и Питтс (1943) :

[3] Рабин и Скотт (1959) :

[4] Гауда, Прабхакар, Применение конечных автоматов

[Mogensen-5] Могенсны, Торбены Эгидии (2011). «Лексический анализ». Введение в дизайн компилятора . Бакалавриат по компьютерным наукам. Лондон: Спрингер. п. 12. DOI : 10.1007 / 978-0-85729-829-4_1 . ISBN 978-0-85729-828-7.

[6] Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг / МА: Эддисон-Уэсли. ISBN 0-201-02988-X.

[Law129-7] а б Лоусон (2004) стр.129

[Sak228-8] Sakarovitch (2009) с.228

[Law128-9] Лоусон (2004) стр.128

[Grusho-10] а б Грушо, AA (1973). «Предельные распределения некоторых характеристик графов случайных автоматов». Математические заметки АН СССР . 4 : 633–637. DOI : 10.1007 / BF01095785 . S2CID 121723743 .

[Cai-11] а б Цай, Син Ши; Деврой, Люк (октябрь 2017 г.). «Структура графа детерминированного автомата, выбранного случайным образом». Случайные структуры и алгоритмы . 51 (3): 428–458. arXiv : 1504.06238 . DOI : 10.1002 / rsa.20707 . S2CID 13013344 .

[12] Карайоль, Арно; Никауд, Кирилл (февраль 2012 г.). Распределение количества доступных состояний в случайном детерминированном автомате . STACS'12 (29-й симпозиум по теоретическим аспектам информатики). 14 . Париж, Франция. С. 194–205.

[Sak105-13] Sakarovitch (2009) стр.105

[Law63-14] Lawson (2004) стр.63

[15] ttps://www7.in.tum.de/um/courses/auto/ws1718/slides1718/04-Implementations_sets.pdf

[Law46-16] Лоусон (2004), стр.46

[Complexity_of_Automaton_Identificat-17] Голд, EM (1978). «Сложность идентификации автоматов по заданным данным» . Информация и контроль . 37 (3): 302–320. DOI : 10.1016 / S0019-9958 (78) 90562-4 .

[18] De Vries, A. (28 июня 2014 г.). Конечные автоматы: поведение и синтез . ISBN 9781483297293.

[19] Лэнг, Кевин Дж. (1992). «Случайные DFA можно приблизительно узнать из редких однородных примеров». Материалы пятого ежегодного семинара по теории вычислительного обучения - COLT '92 . С. 45–52. DOI : 10.1145 / 130385.130390 . ISBN 089791497X. S2CID 7480497 .

[20] Oncina, J .; Гарсия, П. (1992). «Вывод регулярных языков в полиномиальное обновленное время». Распознавание образов и анализ изображений . Серия по машинному восприятию и искусственному интеллекту. 1 . С. 49–61. DOI : 10.1142 / 9789812797902_0004 . ISBN 978-981-02-0881-3.

[21] Лэнг, Кевин Дж .; Перлмуттер, Барак А .; Прайс, Родни А. (1998). «Результаты конкурса Abbadingo one DFA по обучению и новый алгоритм слияния состояний на основе фактических данных» Грамматический вывод (PDF) . Конспект лекций по информатике. 1433 . С. 1–12. DOI : 10.1007 / BFb0054059 . ISBN 978-3-540-64776-8.

[22] «За пределами EDSM | Труды 6-го Международного коллоквиума по грамматическому выводу: алгоритмы и приложения» .

[23] Лукас, SM; Рейнольдс, Т.Дж. (2005). «Изучение детерминированных конечных автоматов с интеллектуальным эволюционным алгоритмом маркировки состояний». IEEE Transactions по анализу шаблонов и машинному анализу . 27 (7): 1063–1074. DOI : 10.1109 / TPAMI.2005.143 . PMID 16013754 . S2CID 14062047 .

[HW1-24] Heule, MJH (2010). Точная идентификация DFA с помощью решателей SAT . Грамматический вывод: теоретические результаты и приложения. ICGI 2010. Конспект лекций по информатике. 6339 . С. 66–79. DOI : 10.1007 / 978-3-642-15488-1_7 .

[25] Heule, Marijn JH; Вервер, Сикко (2013). «Синтез программной модели с использованием решателей выполнимости». Эмпирическая программная инженерия . 18 (4): 825–856. DOI : 10.1007 / s10664-012-9222-Z . ЛВП : 2066/103766 . S2CID 17865020 .

[26] Ульянцев, Владимир; Закирзянов Илья; Шалыто, Анатолий (2015). "Основанные на BFS предикаты нарушения симметрии для идентификации DFA". Язык и теория автоматов и приложения . Конспект лекций по информатике. 8977 . С. 611–622. DOI : 10.1007 / 978-3-319-15579-1_48 . ISBN 978-3-319-15578-4.

[1]