Closure and Decision Properties of Regular Languages: short notes (Theory of Computation)

Revision mode

Introduction

Regular languages are closed under a rich family of operations: Boolean operations, concatenation, star, reverse, homomorphisms and inverse homomorphisms. They also have decidable emptiness, membership, finiteness and equivalence. These facts let you build new regular languages from old ones and answer yes/no questions about DFAs and regular expressions algorithmically.

The skills are the constructions (especially product automata and complement by flipping finals) and knowing which properties remain decidable when you move to context-free languages (many do not).

Prerequisites

Equivalence of Regular Expressions and Finite Automata: DFAs, NFAs and REs as interchangeable presentations.

Core concepts

Closure properties (summary table)

If $L$ and $M$ are regular, so are:

Operation	Construction idea
$L \cup M$	Product with accept when either accepts; or NFA $\varepsilon$ -union; or RE sum
$L \cap M$	Product with accept when both accept
$\overline{L}$	Same DFA, flip accepting/non-accepting (DFA must be complete)
$LM$	NFA: link accepts of $L$ to start of $M$ by $\varepsilon$
$L^*$	NFA star construction (Thompson)
$L^R$	Reverse edges, swap start/accept (NFA; then determinize)
$h(L)$	Homomorphism: replace each edge label $a$ by a path reading $h(a)$
$h^{-1}(L)$	Inverse homomorphism: on $a$ follow the path that $h(a)$ would take in the DFA for $L$

Difference. $L \setminus M = L \cap \overline{M}$ is regular. Symmetric difference likewise.

Further operations that preserve regularity

Operation	Definition	Why regular
Right quotient $L / M$	$\{x \mid xy \in L \text{ for some } y \in M\}$	DFA for $L$ , accept at $q$ iff some $y \in M$ leads from $q$ to $F$ ; true for any $M$ , even non-regular
Left quotient $M \backslash L$	$\{y \mid xy \in L \text{ for some } x \in M\}$	reverse, take right quotient, reverse
Prefixes $\mathrm{Pref}(L)$	all prefixes of strings in $L$	accept every state that can reach $F$
Suffixes, substrings	all suffixes or factors	Suffixes: new epsilon-start to every reachable useful state, retaining original finals. Factors: additionally make every useful state accepting
Substitution by regular languages	replace each $a$ by a regular $L_a$	substitute $L_a$ for $a$ in the expression
$\mathrm{half}(L)$	$\{x \mid xy \in L, \lvert x \rvert = \lvert y \rvert\}$	product of a forward and a guessed backward run
Finite union, finite intersection		repeat the binary constructions

Operations that do not preserve regularity.

Infinite union. Each $\{a^n b^n\}$ is finite, hence regular, but $\bigcup_{n \ge 0} \{a^n b^n\}$ is not regular. Closure holds only for finitely many operands.
Subset. $\{a^n b^n\} \subseteq \{a,b\}^*$ ; a subset of a regular language can be anything.
Going backwards. $L_1 \cup L_2$ regular does not make $L_1, L_2$ regular (take $L_2 = \overline{L_1}$ for a non-regular $L_1$ ); $L_1 L_2$ regular does not either; $L^*$ can be regular when $L$ is not (for $L = \{a^p \mid p \text{ prime}\}$ , $L^* = \{\varepsilon\} \cup \{a^n \mid n \ge 2\}$ ).
Regular with non-regular. $R \cap N$ and $R \cup N$ can go either way. $\emptyset \cap N = \emptyset$ is regular; $\Sigma^* \cap N = N$ is not.

Using closure to prove non-regularity

If $L$ were regular, then $L \cap R$ , $\overline{L}$ and $h(L)$ would be regular for every regular $R$ and homomorphism $h$ . So reduce to a known non-regular language:

$L_{=} = \{ w \in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$ : $L_{=} \cap a^* b^* = \{a^n b^n\}$ , not regular, so $L_{=}$ is not regular.
$L_{\ne} = \{ a^n b^m \mid n \ne m \}$ : $\overline{L_{\ne}} \cap a^* b^* = \{a^n b^n\}$ , so $L_{\ne}$ is not regular. This is far shorter than pumping $L_{\ne}$ directly, where every decomposition seems to survive.
By contrast $\{a^n b^m \mid n + m \text{ even}\}$ is $a^* b^*$ intersected with the even-length strings, so it is regular. Counting two things against each other breaks regularity; checking a parity does not.

Decision properties

Given a DFA (or RE/NFA converted to DFA):

Question	Decidable?	Method
Is $w \in L$ ?	yes	Run the DFA
Is $L = \emptyset$ ?	yes	Reachability from start to some accept state
Is $L = \Sigma^*$ ?	yes	Emptiness of the complement
Is $L$ finite?	yes	In the DFA, after removing dead/unreachable states, check for a cycle on a path from start to an accept
Is $L = M$ ?	yes	Emptiness of symmetric difference, or minimize both and compare
Is $L \subseteq M$ ?	yes	Emptiness of $L \setminus M$

All of the above are decidable in time polynomial in the DFA size for standard formulations used in GATE.

How it works

Product construction for intersection

DFAs $M_1 = (Q_1,\Sigma,\delta_1,q_1,F_1)$ and $M_2 = (Q_2,\Sigma,\delta_2,q_2,F_2)$ . Product:

Q = Q_1 \times Q_2, \quad \delta((p,r),a) = (\delta_1(p,a),\delta_2(r,a)), \quad \text{start } (q_1,q_2),

accept $F_1 \times F_2$ for intersection, or $(F_1 \times Q_2) \cup (Q_1 \times F_2)$ for union.

Complement pitfall

Flipping finals works only on a total DFA. If you flip an NFA's finals, you do not get the complement. Always determinize (and complete) first.

Product automaton for intersection of even-length and ends-with-1 — Figure 1. Product DFA for even-length strings intersected with strings ending in 1; states are pairs (parity, last-bit), and only (even,1) accepts.

Algorithms and pseudocode

Text

INTERSECT(M1, M2)
1  build product with F <- F1 x F2
2  return reachable component from (q1,q2)

EQUIVALENT(M1, M2)
1  M <- INTERSECT(M1, COMPLEMENT(M2)) union INTERSECT(COMPLEMENT(M1), M2)
2  return EMPTY(M)

FINITE(M)
1  remove unreachable states from start and states that cannot reach an accept
2  return whether the remaining graph is acyclic

Mathematical explanation

Why complement needs determinism

An NFA accepts if some path accepts. The language of paths that all reject is a universal condition, which an NFA (existential) cannot express by merely swapping finals. Example: NFA for strings ending with 0; flipping finals does not yield "does not end with 0".

Homomorphism

A homomorphism $h: \Sigma^* \to \Gamma^*$ is determined by $h(a)$ for $a \in \Sigma$ and extended by $h(uv)=h(u)h(v)$ , $h(\varepsilon)=\varepsilon$ . Regular languages are closed under $h$ and under $h^{-1}$ . Inverse homomorphism is especially useful in proofs that a language is regular: express it as $h^{-1}$ of a known regular language.

Worked examples

Example 1: even length $\cap$ ends with 1

DFA even: states E/O. DFA ends-with-1: S/T. Product accept only (E,T). Strings: 01 length 2 ends with 1, accept; 1 length 1, reject; 11 length 2 ends with 1, accept; 0 reject.

Example 2: equivalence via minimization

Two DFAs for "ends with 0" that differ by unreachable states become identical after minimize; EQUIVALENT returns true.

Example 3: reverse of `0*1`

$L = L(0^* 1)$ . Then $L^R = L(1 0^*)$ . Construction: reverse the obvious 2-state NFA and determinize.

Example 4: finiteness

$L(a^*)$ has a cycle through an accept state: infinite. $L(a+aa)$ as a DFA has no cycle among useful states: finite (two nonempty strings plus optionally $\varepsilon$ if present). Language $\{a,aa\}$ is finite.

Example 5: quotient and inverse homomorphism

Quotient: $L = (ab)^*$ and $M = \{b\}$ . Then $L / M = \{x \mid xb \in (ab)^*\} = (ab)^* a$ . With $M = b^*$ the quotient also contains $L$ itself (take $y = \varepsilon$ ): $L / b^* = (ab)^* + (ab)^* a$ .

Inverse homomorphism: let $h(0) = ab$ , $h(1) = \varepsilon$ and $L = (ab)^*$ . Every $h(w)$ is $(ab)^k$ with $k = \#_0(w)$ , so $h^{-1}(L) = \{0,1\}^*$ . With $L' = (ab)(ab)$ (exactly two copies), $h^{-1}(L') = \{ w \mid \#_0(w) = 2 \} = 1^* 0 1^* 0 1^*$ .

Example 6: the finiteness test by lengths

For a DFA with $n$ states, $L$ is infinite iff $L$ contains a string $w$ with $n \le |w| < 2n$ . For the 2-state "even length" DFA, ab has length 2 in $[2, 4)$ : infinite. For a minimal DFA of $\{a, aa\}$ (4 states with the dead state), no accepted string has length in $[4, 8)$ : finite. This turns the cycle test into a bounded membership search.

Example 7: non-closure red herrings

Regular languages are closed under the operations above. Do not confuse them with CFLs (not closed under intersection or complement). Keep the tables separate.

Important properties and observations

Closure under complement + union yields closure under all Boolean operations.
Decision procedures assume an effective representation (DFA/NFA/RE); an arbitrary set given only as a black box is a different story.
Product of $n$ -state and $m$ -state DFAs has at most $nm$ states.
Completing a partial DFA adds at most one dead sink.

Common misconceptions.

Flipping NFA finals for complement.
Claiming equivalence of regular languages is undecidable (it is decidable; CFL equivalence is undecidable).
Thinking intersection of regular languages may leave the class (it does not).

GATE examination perspective

PRODUCT DRILLS. Draw both union and intersection accept conditions.
COMPLEMENT ON DFA ONLY. State the completeness assumption.
DECIDABILITY CONTRAST. Regular: equivalence decidable. CFL: equivalence undecidable. RE (r.e.): emptiness undecidable.
FINITE VS INFINITE. Look for cycles that can pump a nonempty string inside an accepting path, or use the length window $[n, 2n)$ .
FINITE OPERANDS ONLY. Closure under union and intersection is for finitely many languages; an infinite union of regular languages can be any language.
"IF $L_1 \cup L_2$ IS REGULAR THEN ...". Statements that infer regularity of the parts from the whole are false; look for a complement pair.
QUOTIENT. $L / M$ is regular for regular $L$ and any $M$ ; the construction may not be effective when $M$ is not regular, but the language is still regular.
CLOSURE AS A PROOF TOOL. Intersect with $a^* b^*$ or complement to reach $a^n b^n$ ; it is usually shorter than pumping.
FULL CROSS-CLASS TABLE. Closure across regular, DCFL, CFL, CSL, recursive and RE languages, with counterexamples, is collected in Closure and Decision Properties of CFLs.

Summary

Sources

J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson Addison-Wesley, Section 4.2 (closure under Boolean operations, reversal, homomorphisms, inverse homomorphisms), Section 4.3 (decision properties: emptiness, membership), Section 4.4.2 (testing equivalence of regular languages).
M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning: Section 1.1 (the regular operations), Section 1.2 (closure under the regular operations), Section 4.1 (decidable problems concerning regular languages).
P. Linz, An Introduction to Formal Languages and Automata, 6th ed., Jones & Bartlett Learning: Section 4.1 (closure properties of regular languages, including closure under other operations), Section 4.2 (elementary questions about regular languages).