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

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

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

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


dfa regular-language computation-theory nfa
person Utsab    schedule 12.12.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Для входных данных приведен алгоритм, который определяет, является ли L(N1) ∩ L(N2) = ∅:

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

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

person Patrick87    schedule 12.12.2018