Нахождение наименьшего DFA, который разделяет два слова без использования перебора?

23

Учитывая две строки x и y, я хочу создать DFA минимального размера, который принимает x и отклоняет y. Один из способов сделать это - перебор. Вы перечисляете DFA, начиная с самого маленького. Вы пробуете каждый DFA, пока не найдете тот, который принимает x и отклоняет y.

Я хочу знать, есть ли другой известный способ найти или создать DFA минимального размера, который принимает x и отклоняет y. Другими словами, можем ли мы победить перебор?

Подробнее:

(1) Я действительно хочу, чтобы алгоритм нашел DFA минимального размера, а не DFA минимального размера.

(2) Я не просто хочу знать, насколько большой или маленький минимальный DFA.

(3) Здесь я сосредоточен только на том случае, если у вас есть две строки x и y.


Редактировать :

Дополнительная информация для заинтересованного читателя:

Предположим, что и y - двоичные строки длиной не более n . Известно, что существует DFA, который принимает x и отклоняет y не более ИксYNИксY государств. Обратите внимание, что есть околоnN DFA с бинарным алфавитом и не болееNN государств. Следовательно, подход грубой силы не потребует от нас перечислять более чемnN DFA. Отсюда следует, что метод грубой силы не может занять намного больше, чемnNN раз.NN

Слайды, которые я нашел полезными: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf

Майкл Вехар
источник
2
@ AndrásSalamon Является ли все еще NP-полным, если наборы для различения состоят только из одной строки? Мне кажется, что это должно быть разумно поддающимся решению.
Мхум
6
@mhum проблема в том, что есть много разных регулярных языков, которые разделяют две строки - минимизация DFA найдет лучший автомат для любого из этих языков, но ничего не сделает, чтобы сравнить его с автоматами для других разделяющих языков.
Дэвид Эппштейн
4
Если и y имеют разную длину, то при большем из длины n легко быстро найти DFA с O ( log n ) состояниями, которые разделяют их: просто используйте цикл длины p , где p не делит | х | - | YxYNО(журналN)пп, Найдите p , попробовав 2 , 3 , 5 , по порядку, пока не найдете подходящий p . Если x и y имеют одинаковую длину, то O|x||y|p2,3,5,pxyконструкция Робсона в статье 1996 года дает простую машину, которую можно найти с помощью поиска размераO(n). Ни одна из конструкций не гарантированно является самой маленькой DFA. O(n)O(n)
Джеффри Шаллит
3
Заметки Шаллита, ссылки на которые приведены выше, включают полезное наблюдение о том, что наихудший случай проблемы разделения - это когда двоичный алфавит: всегда можно разбить большие алфавиты на два подмножества, которые по-прежнему различают два входных слова, и искать двоичный автомат, который обрабатывает буквы в одном подмножестве как 0 и буквы в другом подмножестве как 1. Но для поиска минимального разделяющего автомата это, кажется, не помогает, потому что вы могли бы использовать дополнительную информацию из исходного алфавита, чтобы добиться большего успеха, чем при сопоставлении с двоичным алфавитом.
Дэвид Эппштейн
3
частный случай этого другого недавнего вопроса, где размеры входных и выходных элементов равны 1. минимальные конечные автоматы, заданные в словах и в словах . В этом ответе перечислены некоторые учебные материалы, включая некоторые эвристические.
vzn

Ответы:

9

Если бы мне пришлось делать это на практике, я бы использовал SAT-решатель.

Вопрос о том, существует ли DFA с состояниями, который принимает x и отклоняет y, можно легко выразить как экземпляр SAT. Например, один способ состоит в том, чтобы иметь 2 k 2 булевых переменных: z s , b , tkxy2k2zs,b,t истинно, если DFA переходит из состояния в состояние t на входном бите b . Затем добавьте несколько предложений, чтобы убедиться, что это DFA, а некоторые переменные и предложения, чтобы убедиться, что он принимает x и отклоняет y .stbxy

Теперь используйте бинарный поиск по чтобы найти наименьшее k такое, что существует DFA такого типа. Исходя из того, что я прочитал в статьях по связанной проблеме, я ожидал, что это может быть достаточно эффективным на практике.kk


Возможны другие кодировки этого как SAT. Например, мы можем использовать кодировку трассировки:

  • Если имеет длину m , вы можете добавить m lg k булевых переменных: пусть s 0 , s 1 , , s m - последовательность состояний, пройденных на входе x , и представлять каждое s i с помощью булевых переменных lg k .xmmlgks0,s1,,smxsilgk

  • Теперь для каждого такого, что x i = x j , у вас есть ограничение, что s i - 1 = s j - 1i,jxi=xj .si1=sj1si=sj

  • Затем расширим это, чтобы обработать : пусть t 0 , , t n будет последовательностью состояний, пройденных на входе y , и представит каждое t j, используя логические переменные lg k . Для каждого i , j такого, что y i = y j , добавьте ограничение, что t i - 1 = t j - 1yt0,,tnytjlgki,jyi=yj .ti1=tj1ti=tj

  • Аналогично, для каждого такого, что x i = y j , добавьте ограничение, котороеi,jxi=yj .si1=tj1si=tj

  • Обе трассы должны начинаться с одной и той же начальной точки, поэтому добавьте требование, что (WLOG вы можете требоватьs0=t0 ).s0=t0=0

  • Чтобы гарантировать, что DFA использует только состояний, требуется, чтобы 0 s i < k и 0 tk0sя<К для всех i , j .0TJ<Кя,J

  • Наконец, чтобы закодировать требование, что принят и уИксY отклонено, требуется, чтобы .sмTN

Все эти требования могут быть закодированы как пункты SAT.

Как и раньше, вы бы использовали бинарный поиск на чтобы найти наименьшее k, для которого существует такой DFA.КК

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