Наименьший DFA, который принимает данные строки и отклоняет другие данные строки

11

Учитывая два набора строк над алфавитом , можем ли мы вычислить наименьший детерминированный конечный автомат (DFA) такой, что и ? $A,B$ $\Sigma$ $M$ $A \subseteq L(M)$ $L(M) \subseteq \Sigma^*\setminus B$

Другими словами, представляет собой набор положительных примеров. Каждая строка в должна быть принята DFA. представляет собой набор отрицательных примеров. Никакая строка в должна быть принята DFA. $A$ $A$ $B$ $B$

Есть ли способ решить эту проблему, возможно, с использованием методов минимизации DFA ? Я мог бы представить себе создание DFA-подобного автомата, который имеет три вида состояний: принимающие состояния, отклоняющие состояния и состояния "не заботятся" (любой вход, заканчивающийся в состоянии "не заботиться", может быть принят или отклонено). Но можем ли мы найти способ свести это к обычному DFA?

Вы можете думать об этом как о проблеме изучения DFA, используя положительные и отрицательные примеры.

Это вдохновлено Regex Golf NP-Complete? , который задает аналогичные вопросы для регулярных выражений вместо DFA.

1

Я думаю, вам нужно наложить какие-то ограничения на то, какими могут быть языки

и

и как они могут быть указаны.

A

$A$

B

$B$

reinierpost

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

Рафаэль

7

DFA, как вы описываете, называется разделительным DFA . Существует некоторая литература по этой проблеме, когда и являются обычными языками, такие как « Изучение минимального разделения DFA для проверки композиции», Ю-Фанг Чен, Азаде Фарзан, Эдмунд М. Кларк, Йих-Куен Цай, Боу-Яу Ван $A$ $B$

Обратите внимание, что, как утверждает @reinierpost, без каких-либо ограничений на A и B проблема может стать неразрешимой.

Shaull
источник

Если A и B оба являются обычными языками, и если кому-то разрешено произвольно принимать или отклонять любые входные данные, для которых A и B дали бы один и тот же результат, я не понимаю, как проблема может быть неразрешимой. Для DFA любого конкретного размера можно было бы создать полный набор входных данных, которые он должен принимать, и входных данных, которые он должен отклонять, так что любой DFA с тем же числом состояний или меньше, который правильно обрабатывает все тестовые примеры может гарантированно вести себя одинаково во всех случаях. Так как машина, которая принимает все, А принимает и отклоняет все остальное ...

суперкат

... удовлетворяя ограничениям, можно наложить верхний предел на число состояний, которые должна содержать машина; поскольку существует конечное число возможных машин любого заданного размера и конечное число тестовых случаев, которые можно оценить, можно сгенерировать все возможные машины, которые меньше А, и посмотреть, удовлетворяет ли какая-либо из них необходимым условиям. Не совсем быстрый способ решения проблемы, но, безусловно, разрешимый, если A и B регулярны. Если они не регулярные, DFA не сможет решить A или B. «Разница» может иногда быть регулярной, даже если A и B нет, но это ...

суперкат

... было бы "необычным" случаем.

суперкат

8

$A$ $B$ $A \cap B = \emptyset$ $A$ $A \cap B \neq \emptyset$

Нахождение минимального DFA, соответствующего данному набору строк, является NP-полным. Этот результат представлен в виде теоремы 1 в статье Англуина « О сложности минимального вывода регулярных множеств» . Очевидно, что ваша проблема также является NP-полной.

За множеством хороших ссылок и обсуждений по изучению обычных языков обращайтесь к посту блога CSTheory « Об изучении обычных языков» .

альт
источник

Если бы требования были изменены таким образом, чтобы автомат мог произвольно принимать или отклонять что-либо, находящееся как в A, так и в B, то проблема всегда была бы разрешима для любых A и B; если поиск оптимального автомата был бы NP-полным без этого, он был бы NP-полным даже с этим требованием.

суперкат

Наименьший DFA, который принимает данные строки и отклоняет другие данные строки

Ответы: