# Lecture 5: Closure Properties

We will show that the set of regular languages is closed under basic set-theoretic operations, intersection, union, and complement.

These closure properties are useful to show that languages are regular or to show that they are not.

Theorem: Let $A, B\subseteq \Sigma^\ast$ be two regular languages over $\Sigma$. Then, the following languages are also regular:

• intersection: $A\cap B=\{ w \in \Sigma^\ast \mid w\in A \text{ and } w\in B \}$,
• union: $A \cup B=\{ w\in\Sigma^\ast \mid w\in A \text{ or } w\in B\}$,
• complement: $\bar A=\{ w\in \Sigma^\ast \mid w\notin A\}$ and $\bar B=\{w\in\Sigma^\ast \mid w\notin B\}$.

Furthermore, if $M_A$ and $M_B$ are DFAs for $A$ and $B$, then the languages above have DFAs with a number of states that is polynomial in the number of states of $M_A$ and $M_B$.

Proof: Suppose $M_A$ and $M_B$ are deterministic finite automata for $A$ and $B$. Let $\delta_A{\colon}{} Q_A\times \Sigma\to Q_A$ and $\delta_B{\colon}{} Q_B\times \Sigma\to Q_B$ be the transition functions of $M_A$ and $M_B$. Here, $Q_A$ and $Q_B$ are the states sets of $M_A$ and $M_B$. Let $F_A\subseteq Q_A$ and $F_B \subseteq Q_B$ be the accept states of $M_A$ and $M_B$.

Complement: We are to construct a DFA $M$ for the complement $\bar A$. Let $M$ be the same automaton as $M_A$ except with accept states $F = Q_A\setminus F_A$. (Concretely, $M$ has the same transition function, set of states, alphabet, and start state as $M_A$.) Then, $M$ accepts a word $w\in\Sigma^\ast$ if and only if $\delta^\ast(w)\in F=Q_A\setminus F_A$. By construction, $M_A$ is in the same state after reading $w$, i.e., $\delta^\ast(w)=\delta_A^\ast(w)$. Hence, $M$ accepts $w$ if and only if $\delta_A(w)\notin F_A$, which means that $M_A$ does not accept $w$. It follows that $L(M) = \Sigma^\ast \setminus L(M_A)= \bar A$.

Intersection: We are to construct a DFA $M$ for the intersection $A\cap B$. The idea is that $M$ simulates both $M_A$ and $M_B$ at the same time. The state space of $M$ is the product set $Q=Q_A\times Q_B$. The transition function is $\delta\bigl((q_A,q_B),x\bigr) = \bigl(\delta_A(q_A,x), \delta_B(q_B,x)\bigr)$ The start state of $M$ has the start space of $M_A$ in the first coordinate and the start space of $M_B$ in the second coordinate. Finally the accept states of $M$ are $F=F_A\times F_B$. With this construction, $M$ is in state $\delta^\ast (w)=\bigl(\delta_A^\ast(w),\delta_A^\ast(w)\bigr)$ after reading $w$. Hence, $M$ accepts $w$ if and only $\delta_A^\ast(w)\in F_A$ and $\delta_B^\ast(w)\in F_B$, which means that $w\in A\cap B$.

Union: We could construct an automaton for $A\cup B$ similar to the product construction above. However, we can also use the properties we have proved so far to conclude that $A\cup B$ is regular whenever $A$ and $B$ are regular. By de Morgan’s law, we can express the union in terms of complements and intersection, $A\cup B=\overline{(\bar A \cap \bar B)}$. Since we have already shown that regular languages are closed under complement and intersection, it follows that $A\cup B$ is regular.