Closure of Regular Languages

By the definition of regular expressions (and by Thompson's algorithm), we know that the union, concatenation and Kleene closure of regular languages must also be a regular language. It is reasonable to ask: does this hold for other ``set-theoretic'' operations, such as intersection, difference and complement? We prove that these languages are regular by constructing the appropriate automata.

Let $L_1$ and $L_2$ be regular languages over the alphabet $\Sigma$, and let $M_1$ and $M_2$ be their corresponding total DFAs.

Let us define the components of $M_1$ and $M_2$ as follows:

• let the set of states of $M_1$ be $P$, from which we distinguish:
  • $p_0$, the start state of $M_1$
  • $P_f$, the set of final states of $M_1$
• let $D_1$ be the transition function for $M_1$; that is, the (partial) function:
  $D_1$ : $P\; \times\; \Sigma\; \longrightarrow\; P$
• let the set of states of $M_2$ be $Q$, from which we distinguish:
  • $q_0$, the start state of $M_2$
  • $Q_f$, the set of final states of $M_2$
• let $D_2$ be the transition function for $M_2$; that is, the (partial) function:
  $D_2$ : $Q\; \times\; \Sigma\; \longrightarrow\; Q$
  

Now we can define:

1. The intersection of $L_1$ and $L_2$ is the machine $M_1 \cap M_2$ defined by:
   • the set of states is $P\; \times\; Q$, the Cartesian product of $P$ and $Q$. Thus for any $p\, \in\, P$ and $q\, \in\, Q$, the pair $(p,q)$ is a state. We distinguish:
     • $(p_0,q_0)$, the start state of $M_1 \cap M_2$
     • $\{(p,q)\; \mid\; p\, \in\, P_f\; and\; q\, \in\, Q_f\}$, the set of final states of $M_1 \cap M_2$
   • the transition function: $D_{P \times Q}$ : $(P \times Q)\; \times\; \Sigma\; \longrightarrow\; (P \times Q)$ is defined, for any character `a', by: $D_{P \times Q}((p,q),a)\; =\; (D_1(p,a),\, D_2(q,a))$
     

2. The difference of $L_1$ and $L_2$ is the machine $M_1 - M_2$, defined as for intersection, except that the set of final states is now: $\{(p,q)\; \mid\; p\, \in\, P_f\; and\; q\, \not\in\, Q_f\}$
   

3. The complement of the language $L_1$ is the machine $M_1$', which is simply $M_1$ with the final and non-final states swapped; ie. the set of final states is: $P\, - \, P_f$