Построить DFA из языка L = {L1 \ L2}

Question

Как я могу построить ДКА из языка L = {L1 \ L2}

ДКА из L1 и L2 заданы, но как я могу " вычесть "один DFA из другого? Возможно ли это с относительным дополнением http://en.wikipedia.org/wiki/Complement_(set_theory) и законом Де Морганса?

Мое решение:

Answer 1

В моем понимании, желаемый DFA может быть получен с помощью модифицированного автомата продукта, используемый для пересечения L1 и L2, но терминальные состояния имеют определяться по-разному. Вместо того, чтобы состояние продукта (q_1,q_2) терминальное состояние, если и только если q_1 и q_2 терминальные состояния в A(L1) и A(L2) соответственно, определить его быть конечным состоянием тогда и только тогда, когда q_1 является конечным состоянием и q_2 является не терминала государство.

Я не совсем уверен, что помимо этого элементарного аргумента результат может быть применен заданной формулировкой De Morgan's law.