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.