Question

Let A and B be regular languages. Show that A \ B is also regular. (Recall that A \ B = {x ∈ A | x ∉ B}. In other words, this operation removes from A all the strings that are also in B.)

Answer 1

Let M1 be the DFA that accepts A and M2 be the DFA that accepts B.

We create a DFA M that accepts A\B.

Let Q1 be the set of states of M1 and Q2 be the set of states of M2.

We define Q=Q1xQ2 to be the set of states of M where Q1xQ2 represents the Cartesian product of Q1 and Q2.

Let d1 and d2 be the transition functions of M1 and M2 respectively. We define the transition function of M to be d where, if Qa be a state in M1 and Qb be a state in M2, and a be an alphabet then, d((qa,qb),a)=d(qa,a),d(qb,a).

If q1 and q2 be the initial states of M1 and M2 respectively then (q1,q2) is the initial state of M.

We make the accept states of M to be those states where the state from M1 is final but that from M2 is not.

The DFA M we constructed accepts only those strings which are accepted by A but rejected by B. Hence A\B is a regular language.