Question

how to solve the Under Problem?

can i see the answer?

--------------------------------------------------------------

introduction To Automata Theory Languages , and Computation
Prentice Hall; 2nd edition

Exercise 4.2.14: In Theorem 4.8, we described the "product construction" that took two DFA's and constructed one DFA whose language is the intersection of the languages of the first two.

c)Show how to modify the product construction so the resulting DFA accepts the difference of the languages of the two given DFA's.

Answer 1

Answer

Let M and N be the languages of DFA's A_M and A_N, where

$A_M=(Q_M,\Sigma ,\delta_M,q_M,F_M)$

$A_N=(Q_N,\Sigma ,\delta_N,q_N,F_N)$

The product construction of above two DFA's is

$A=(Q_M\times Q_N,\Sigma ,\delta,(q_M,q_N),F)$

where δ( (p, g), a)-@w (p, a), bylg, a) )

As we want to accept the difference of the languages of the two given DFA's, we will choose as the accepting states of A all those pairs (p,q) where p is is an accepting state of A_M and q is a non-accepting state of A_N.

That means,

${\color{Blue} F=F_M \times \left ( Q_N-F_N \right )}$

Then the resulting DFA accepts the difference of the languages M - N.