Учитывая два регулярных выражения, определите, является ли один дополнением к другому

Question

Я хотел бы знать, как вы можете определить, является ли какое-либо регулярное выражение дополнением к другому регулярному выражению.Допустим, у меня есть 2 регулярных выражения r_1 и r_2.Я могу, конечно, создать DFA из каждого из них, а затем проверить, чтобы убедиться, что L (r_1)! = L (r_2).Но это не обязательно означает, что r_1 является дополнением к r_2 и наоборот.Кроме того, кажется, что много разных регулярных выражений могут быть одним и тем же дополнением к одному регулярному выражению.Поэтому мне интересно, как по двум регулярным выражениям я могу определить, является ли одно дополнением другого.Это также ново для меня, поэтому, возможно, я упускаю что-то, что должно быть очевидным.

Редактировать: Я должен отметить, что я не просто пытаюсь найти дополнение регулярного выражения.Мне дано два регулярных выражения, и я должен определить, являются ли они дополнением друг друга.

Answer 1

Вот один подход, который концептуально прост, если не ужасно эффективен (не то, что обязательно есть более эффективное решение ...):

1. Создайте NFA M и N для регулярных выражений r ис соответственно.Вы можете сделать это с помощью конструкции, введенной в доказательстве того, что конечные автоматы описывают одни и те же языки.
2. Определите M и N, чтобы получить M 'и N'.Мы могли бы также пойти дальше и минимизировать их на этом этапе ... давая M '' и N ''.
3. Построить машину C, используя машинную конструкцию декартовых произведений на машинах M '' и N ''.Прием будет определяться критерием симметричной разности или XOR: принимающие состояния в машине продукта соответствуют парам состояний (m, n), где в автомате принимается ровно одно из двух состояний.
4. СвернутьC и назовите результат C '
5. Если L (r) = L (s)', то начальное состояние C 'будет принимать, и C' будет иметь все переходы, исходящие из исходного состояния, также заканчивающиеся вначальное состояние.Если это так,

Почему это должно работать?Симметричная разность двух множеств - это совокупность всего ровно одного (ни того, ни другого, ни того и другого).Если L (s) и L (r) дополняют друг друга, нетрудно увидеть, что симметричное различие включает в себя все строки (по определению, дополнение набора содержит все, что не входит в набор).Предположим, что теперь существуют некомплементарные множества, симметричное различие которых является вселенной всех строк.Множества не являются дополнительными, поэтому (1) их объединение не пусто или (2) их объединение не является универсумом всех строк.В случае (1) симметричная разность не будет включать общий элемент;в случае (2) симметричное различие не будет включать отсутствующие строки.Таким образом, только дополнительные множества имеют симметричную разность, равную вселенной всех строк;и минимальный DFA для набора всех строк всегда будет иметь принимающее начальное состояние с самоконтролями.

Answer 2

Для дополнения: L (r_1) ==! L (r_2)