The minus operator on sets is usually defined as A B x I x

The minus operator on sets is usually defined as: A - B = {x I x A and x B}. Prove that the class of sets accepted by finite automata is closed under minus.

Solution

A-B is the same is A B\' . We know that A and B are regular, and if B is regular B\' is also regular. We already know that regular languages are closed under . So A-B is regular if both A,B are regular. Being a regular language is same as having a finite automata, so - is also closed by finite automata.