Q4Theory of Computation

A class of languages is said to be closed under an operation if applying that operation to language(s) from the class always yields a language that is also in the class. For regular languages, closure is proved constructively: given automata or regular expressions for the input languages, we exhibit an automaton or regular expression for the result, which by Kleene's Theorem guarantees the result is regular.

• Union: If $L_1,L_2$ are regular with DFAs $M_1,M_2$, build a product automaton whose states are pairs $(q_1,q_2)\in Q_1\times Q_2$, transitioning both components in parallel, with final states any pair where either component is final. Equivalently, if $L_1,L_2$ have regular expressions $r_1,r_2$, then $r_1+r_2$ describes $L_1\cup L_2$.
• Intersection: Using the same product construction, but making a pair final only when both components are final. This proves $L_1\cap L_2$ is regular.
• Complement: Given a DFA $M$ for $L$ (must be a complete DFA, total transition function), swap final and non-final states: $F^{\prime }=Q-F$. The resulting DFA accepts exactly ${\Sigma }^{\ast }-L$.
• Concatenation: If $L_1,L_2$ are regular with expressions $r_1,r_2$, then $r_1{r}_2$ describes $L_1{L}_2=\{xy\mid x\in L_1,y\in L_2\}$; equivalently, NFAs can be joined with an $ϵ$-transition from each final state of $M_1$ to the start state of $M_2$.
• Kleene star: If $r$ describes $L$, then $r^{\ast }$ describes $L^{\ast }=\{x_1{x}_2\cdots x_k\mid k\ge 0,x_i\in L\}$, constructed by adding $ϵ$-loops back to the start state at each accepting state.
• Reversal: If $L$ is regular with DFA $M$, reversing all transition arrows, swapping the start and final-state roles (making the old start state the new unique final state and adding a new start state with $ϵ$-transitions to the old final states) yields an NFA for $L^R=\{w^R\mid w\in L\}$.
• Homomorphism and inverse homomorphism: If $h:\Sigma \to {\Delta }^{\ast }$ is a homomorphism and $L$ is regular, then $h(L)$ is regular (substitute each symbol's regular-expression image into the expression for $L$); likewise $h^{-1}(L)$ is regular.
• Set difference: Since $L_1-L_2=L_1\cap \overline{L_2}$, and regular languages are closed under both intersection and complement, difference follows directly.

Let $M_1=(Q_1,\Sigma ,{\delta }_1,s_1,F_1)$ and $M_2=(Q_2,\Sigma ,{\delta }_2,s_2,F_2)$ recognize $L_1$ and $L_2$. Define $M=(Q_1\times Q_2,\Sigma ,\delta ,(s_1,s_2),F_1\times F_2)$ where $\delta ((p,q),a)=({\delta }_1(p,a),{\delta }_2(q,a))$. By induction on $|w|$, the extended transition function satisfies $\hat{\delta }((s_1,s_2),w)=({\hat{\delta }}_1(s_1,w),{\hat{\delta }}_2(s_2,w))$, so $w$ drives $M$ to a state in $F_1\times F_2$ exactly when it drives $M_1$ to a state in $F_1$ and $M_2$ to a state in $F_2$ simultaneously, i.e., $w\in L(M)⟺w\in L_1\cap L_2$. Since $M$ is a well-defined finite automaton with $|Q_1|\cdot |Q_2|$ states, $L_1\cap L_2$ is regular.

These closure properties are the standard toolkit for proving other languages regular (by decomposing them into unions, intersections, and complements of simpler regular languages) and, conversely, are frequently combined with the Pumping Lemma to prove languages are not regular: for example, if $L$ were regular then $L\cap R$ for a simple regular $R$ would also have to be regular, and if it demonstrably is not, $L$ cannot be regular either.