Показывая, что пересечение двух языков, принятых NFA, неразрешимо

Question

У меня проблема с этой проблемой.

Пусть A = {〈N1, N2〉 |N1 и N2 являются NFA и L (N1) ∩ L (N2) = ∅}.Покажите, что А. разрешимо.

Любая помощь приветствуется.

Answer 1

При заданном входном сигнале приведен алгоритм, который определяет, будет ли L (N1) L (N2) = *:

1. определять N1 и N2 в D1 и D2 с использованием конструкции блока питания.медленно, но эффективно.
2. пересекают D1 и D2 в М., используя машинную конструкцию декартового произведения.
3. минимизируют M в M, используя некоторый алгоритм минимизации DFA
4. .имеет принимающее состояние.если так, остановите-отклоните;в противном случае, halt-accept.

Это эффективно вычисляемая процедура для определения включения и / или исключения из набора, поэтому набор может быть разрешен.