Computer science Automata and formal languages Theorem

Closure properties of regular languages

Builds on Regular language Kleene star Homomorphism Deterministic finite automaton

Statement

Let $\Sigma$ and $\Gamma$ be alphabets, and let $K, L \subseteq \Sigma^*$ be regular languages. Then the following languages are regular:

the union $K \cup L$ , the intersection $K \cap L$ , the difference $K \setminus L$ and the complement $\Sigma^* \setminus L$ ;
the concatenation $KL = \set{uv : u \in K,\ v \in L}$ ;
the Kleene star $L^*$ ;
the reversal $L^R = \set{a_n \cdots a_1 : a_1 \cdots a_n \in L}$ ;
the image $h(L)$ and, for a regular $M \subseteq \Gamma^*$ , the preimage $g^{-1}(M)$ , where $h \colon \Sigma^* \to \Gamma^*$ and $g \colon \Sigma^* \to \Gamma^*$ are monoid homomorphisms.

Remarks

Complement: swap accepting and non-accepting states of a complete DFA for $L$ . Intersection: run DFAs for $K$ and $L$ in parallel on the product of their state sets, accepting when both accept; union and difference work the same way. Concatenation, star and reversal are easiest with nondeterministic automata: glue automata with $\varepsilon$ -moves, or reverse all arrows and swap initial and accepting states. For the preimage, a DFA for $g^{-1}(M)$ moves on the letter $a$ the way a DFA for $M$ moves on the word $g(a)$ . For example, the words over $\set{a, b}$ with an even number of $a$ 's and an odd number of $b$ 's form a regular language, as the intersection of two regular languages. The class is not closed under infinite unions: every language is a union of singletons, and $\set{a^n b^n : n \ge 0}$ is not regular.

Going deeper

For a student

Closure properties are a main tool for showing that a language is not regular. For instance, if $L = \set{w \in \set{a, b}^* : w \text{ has as many } a\text{'s as } b\text{'s}}$ were regular, then $L \cap a^* b^* = \set{a^n b^n}$ would be regular, which the pumping lemma rules out. Context-free languages, in contrast, are not closed under intersection or complement. The constructions are effective, so they also give algorithms, for example to decide whether two DFAs accept the same language by testing the symmetric difference for emptiness.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Deterministic finite automaton concept
Homomorphism concept
Kleene star concept
Regular language concept
Closure properties of regular languages statement

Tag	`446KZ8HJ5F`
URI	`m2://446KZ8HJ5F`
Kind	statement, theorem
Writing	W0 stub
MSC	68Q45
Status	This copy of the site has no build data. Run `m2 status 446KZ8HJ5F`.
About	Regular language
Uses	Regular language, Kleene star, Homomorphism, Deterministic finite automaton
Changed	3 November 2026