Is the family of regular languages closed under the operation of set difference?

1.9k Views Asked by Bumbble Comm At 30 Mar 2026 - 6:12

Prove that the family of regular languages is closed under the operation of set difference.

(I tried coming up with an NFA that will recognize the new language, but I get stuck with defining the transition function.)

There are 1 best solutions below

Bumbble Comm On 18 Mar 2016 - 10:11 BEST ANSWER

From set theory we get $$ L_1 \setminus L_2 = L_1 \cap L_2^c $$

So you can reduce this problem to closure of regular languages regarding set intersection and set complement.

Regularity of $L_1 \cap L_2$ should follow from product automaton construction from a DFA for $L_1$ and $L_2$ each.

Set complement should follow from taking a DFA for $L_2$ and turning final states into normal states and vice versa.