Closure Properties of Regular Languages

Overview

Regular languages are closed under many operations, meaning: applying the operation to regular languages yields another regular language.

This is proved using automata or regular expressions.

Union

Theorem: If $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is regular.

Proof (NFA)

Given DFAs $M_1$ and $M_2$:

1. Create new start state $s_0$
2. Add $\varepsilon$-transitions to $s_1$ and $s_2$
3. Accepting states: $F_1 \cup F_2$

Proof (Regex)

If $L_i = L(R_i)$, then $L_1 \cup L_2 = L(R_1 | R_2)$.

Concatenation

Theorem: If $L_1$ and $L_2$ are regular, then $L_1 \cdot L_2$ is regular.

Proof (NFA)

Given NFAs $M_1, M_2$:

1. Add $\varepsilon$-transitions from $F_1$ to $s_2$
2. Start: $s_1$
3. Accepting: $F_2$

Proof (Regex)

If $L_i = L(R_i)$, then $L_1 \cdot L_2 = L(R_1 R_2)$.

Kleene Star

Theorem: If $L$ is regular, then $L^*$ is regular.

Proof (NFA)

1. Create new start/accept state $q_0$
2. Add $\varepsilon$-transition $q_0 \to s$
3. Add $\varepsilon$-transitions from each $f \in F$ to $s$
4. Add $\varepsilon$-transition from each $f \in F$ to $q_0$
5. Accepting: $\{q_0\}$

Proof (Regex)

If $L = L(R)$, then $L^* = L(R^*)$.

Complement

Theorem: If $L$ is regular, then $\bar{L} = \Sigma^* \setminus L$ is regular.

Proof (DFA)

Given DFA $M = (Q, \Sigma, \delta, s, F)$:

Define $\bar{M} = (Q, \Sigma, \delta, s, Q \setminus F)$.

Swap accepting and non-accepting states.

Note: Requires complete DFA (all transitions defined).

Intersection

Theorem: If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is regular.

Proof (DFA Product Construction)

Given DFAs $M_1 = (Q_1, \Sigma, \delta_1, s_1, F_1)$ and $M_2 = (Q_2, \Sigma, \delta_2, s_2, F_2)$:

Define product DFA $M = (Q, \Sigma, \delta, s, F)$:

• $Q = Q_1 \times Q_2$
• $\delta((q_1, q_2), a) = (\delta_1(q_1, a), \delta_2(q_2, a))$
• $s = (s_1, s_2)$
• $F = F_1 \times F_2$

Product accepts iff both components are accepting.

Proof (De Morgan)

$L_1 \cap L_2 = \overline{\bar{L}_1 \cup \bar{L}_2}$

Use closure under complement and union.

Difference

Theorem: If $L_1$ and $L_2$ are regular, then $L_1 \setminus L_2$ is regular.

Proof

$L_1 \setminus L_2 = L_1 \cap \bar{L}_2$

Use intersection and complement.

Homomorphism

Theorem: If $L$ is regular and $h : \Sigma^* \to \Gamma^*$ is a homomorphism, then $h(L)$ is regular.

Proof (Regex)

Apply $h$ to each symbol in the regex.

Inverse Homomorphism

Theorem: If $L \subseteq \Gamma^*$ is regular and $h : \Sigma^* \to \Gamma^*$ is a homomorphism, then $h^{-1}(L)$ is regular.

Proof (DFA)

Given DFA $M$ for $L$, construct $M'$ where:

$\delta'(q, a) = \hat{\delta}(q, h(a))$

Run $M$ on the image of each input symbol.

Reversal

Theorem: If $L$ is regular, then $L^R = \{w^R : w \in L\}$ is regular.

Proof

Reverse all transitions in an NFA, swap start and accept, convert to DFA.

Properties Summary

Operation	Construction	Notes
Union	NFA with $\varepsilon$-edges	Easy
Concatenation	NFA with $\varepsilon$-edges	Easy
Star	NFA with loop back	Easy
Complement	Swap accept/non-accept in DFA	Needs complete DFA
Intersection	Product DFA	Quadratic states
Difference	$L_1 \cap \bar{L}_2$	Via intersection and complement
Reversal	Reverse NFA	Swap start/accept
Homomorphism	Apply to regex	Symbol-wise
Inverse homomorphism	DFA transformation	Efficient

---

Summary

• Regular languages are closed under: $\cup$, $\cdot$, $*$, $\bar{\cdot}$, $\cap$, $\setminus$, reversal
• Union/concat/star: easy with NFAs
• Complement: easy with DFAs, hard with NFAs
• Intersection: product construction or complement + union