Минимальный DFA, удовлетворяющий ограниченному взгляду на язык

Скажем, у кого-то есть язык , но вы не знаете, какие строки на самом деле являются частью языка. Все, что есть, - это конечное представление языка: конечный набор строк о которых известно, что они есть в языке, и конечный набор строк , которые известны не быть на языке.$L \subseteq \Sigma^*$$A \subseteq L$$B \subseteq (\Sigma^* \setminus L)$

Например, допустим, у меня есть и . Я мог бы иметь язык , так как и согласуются с , или я мог бы иметь полностью другой язык.B = { b , a a b , a a a b a } L = { a 2 i + 1 b j | i , j ∈ N } A B $A = \{ab, aaab, aaaaabb\}$$B = \{b, aab, aaaba\}$$L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$$A$$B$$L$

Мой вопрос: существует ли известный способ создания DFA (детерминированных конечных автоматов), который принимает строки в и отклоняет строки в с минимальным или почти минимальным числом состояний? В чем сложность этой проблемы? Насколько это хорошо при аппроксимации (при условии, что имеет довольно низкую описательную сложность, а и большие)?B L L A $A$$B$$L$$L$$A$$B$

Оригинальный вопрос на math.stackexchange.com. Я решил сделать репост здесь, не получив ответов на исходный вопрос и не зная, где их искать. Если бы кто-то мог указать мне на исследования в этой области, это было бы очень ценно.

Как вы уже знаете из комментариев, поиск минимального DFA, удовлетворяющего конечному набору положительных и отрицательных примеров, является -hard. Однако не вся надежда потеряна, если вы захотите немного изменить свою парадигму обучения, тогда мы сможем вернуться в .$\mathsf{NP}$$\mathsf{P}$

Предположим, что вы пытаетесь выучить неизвестный DFA минимальный для некоторого языка . Если вы разрешаете запросы на членство оракула и выступаете в роли учителя, отвечая на следующий вопрос: Учитывая предложенный DFA , распознает ли он ? Если нет, можете ли вы привести контрпример?L W G L $W$$L_W$$G$$L_W$

Обратите внимание, что если оракул имеет доступ к он может сравнить с в поли-времени, так как тестирование равенства между обычными языками легко. Генерация контрпримеров также может быть выполнена за полиномиальное время.G $W$$G$$W$

В этом контексте вы можете выучить за полиномиальное время, используя алгоритм Angluin ( 1987 ; pdf ) (или его уточнение по Шапире ; см. Раздел 5.4.5). Для получения дополнительной информации об этой модели, вот два вопроса о cstheory и CS.SE об этом:$W$

• Нижние границы для обучения в запросе членства и модели контрпримеров

• Есть ли улучшения в алгоритме Даны Англюин для изучения регулярных наборов

Мне кажется, что вы можете использовать уточнение эквивалентности Myhill-Nerode для этой проблемы.

Мы можем определить , если существует таким образом, что и . Это означает, что любой автомат, отделяющий от должен находиться в разных состояниях после чтения и .x ∈ Σ u x ∈ A v x ∈ B A B u $u\nsim v$$x\in\Sigma$$ux\in A$$vx\in B$$A$$B$$u$$v$

Достаточно изучить это соотношение по префиксам элементов и . Это даст вам нижнюю границу количества нужных вам штатов. Я не уверен, что это напрямую дает вам способ построить минимальный автомат, но это по крайней мере путь для исследования.$A$$B$

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

В дополнение к некоторым исследованиям теории КС, цитируемым в комментариях, в этой области также есть некоторые более эмпирические исследования, например, ниже, с использованием ANN для создания FSM из примеров. Обратите внимание, что всегда можно запустить стандартный алгоритм минимизации DFA для результата. Библиотека AT & T FSM хороша для работы в этой области.

Спрашивающий не конкретизирует свою проблемную область, что может помочь понять структуру примеров и получить более конкретные ссылки. Однако, один пример, который можно увидеть, это алгоритмы ИИ в играх, которые используют алгоритмы FSM. Я подозреваю, что в некоторых случаях автоматы изучаются на примерах с использованием алгоритмов обучения.

[1] Изучение класса больших конечных автоматов с рекуррентной нейронной сетью C. Lee Giles, 1, BG Horne, T. Lin 1995

[2] Обучение FSM с самокластеризованными рекуррентными сетями , Zeng & Smyth 1993

[3] библиотека AT & T FSM