Closure properties of regular languages

Why it exists

A class of languages is closed under an operation if applying the operation to members of the class gives a member of the class. For regular languages, closure means we can build a new automaton for the result. Closure is the main tool for two kinds of GATE questions: "is this combined language regular?" and "prove that $L$ is not regular" (if $L$ were regular, then some regular combination of $L$ with a regular language would be a language already known to be non-regular).

Prerequisites

You need DFAs and their minimal sizes (DFA minimisation), the subset construction (subset construction) and the translation between expressions and automata (regex and automata).

Precise definitions

For regular languages $L, L_1, L_2$ over $\Sigma$ the following are all regular:

Not closed. Infinite union and infinite intersection (every finite language is regular, but $\{a^n b^n : n \ge 0\} = \bigcup_n \{a^n b^n\}$ is not); and subsets: a subset of a regular language need not be regular ($\{a^n b^n\} \subseteq a^* b^*$).

How it works

The constructions

Let $D_1, D_2$ be complete DFAs with $m$ and $n$ states.

• Complement. Swap accepting and non-accepting states of the complete DFA. $m$ states. (If the DFA is not complete, add the dead state first, otherwise strings that get stuck would be lost.)
• Product (union, intersection, difference). States are pairs $(p, q)$, moves go in parallel; accept if "$p$ accepts or $q$ accepts" (union), "and" (intersection), "$p$ accepts and $q$ does not" (difference). At most $m n$ states. The bound $m n$ is reached by two independent counters (the number of $a$'s modulo $m$ and the number of $b$'s modulo $n$; checked for four pairs).
• Concatenation. NFA: the two machines side by side, $\varepsilon$ edges from the accepting states of the first to the start of the second. $m + n$ states. The equivalent DFA can have exponentially more (standard result, quoted).
• Star. NFA: a new accepting start state, $\varepsilon$ edges from the accepting states back to the old start. $m + 1$ states.
• Reversal. NFA: reverse every edge, make the old start the only accepting state, add a new start with $\varepsilon$ edges to the old accepting states. $m + 1$ states; the minimal DFA of the reversal can need $2^m$ states.
• Homomorphism. Replace each edge labelled $a$ by a path spelling $h(a)$ (an $\varepsilon$ edge if $h(a) = \varepsilon$).
• Inverse homomorphism. Same states: $\delta'(q, a) = \delta^*(q, h(a))$. At most $m$ states, a DFA directly.
• Quotients and prefixes. Same DFA with a changed accepting set: for $L_1 / L_2$ accept the states from which some string of $L_2$ leads to acceptance (this is a property of the DFA, so $L_2$ can be non-regular); for the prefixes accept all states from which an accepting state is reachable.
• Half. The DFA keeps a pair: the current state $p$ and the set $S_k$ of states from which some string of the length read so far leads to acceptance; accept if $p \in S_k$. Finite, so regular.

Sizes on a small example

$L_1$ = binary strings that end in $01$ ($3$ states), $L_2$ = binary strings with an even number of $1$s ($2$ states). For each operation the table gives the number of states of the machine built and of the minimal DFA of the result.

The union and the intersection are built from $3 \times 2 = 6$ states but both minimise to $4$. Complement does not change the size. The reversal of "ends with $01$" is "starts with $10$", whose minimal DFA has $4$ states (start, after $1$, accepting, dead) even though the original had $3$. The image under $h(0) = 01$, $h(1) = \varepsilon$ is $(01)^+$ (verified), the inverse image under $h(0) = 01$, $h(1) = 1$ is "ends with $0$", and the right quotient $L_1 / 1$ is also "ends with $0$" (both with $2$ states). Every string is a prefix of a string ending in $01$, so the prefix language is $\Sigma^*$ with $1$ state.

Reversal can blow up

Let $L_n$ = "the $n$-th symbol from the start is $1$". Its minimal DFA has $n + 2$ states (count to $n$, then accept or reject, plus a trap). The reversal is "the $n$-th symbol from the end is $1$", whose minimal DFA needs $2^n$ states. Computed for $n = 2, \ldots, 6$: $4, 8, 16, 32, 64$. So an $n$-state DFA can need about $2^n$ states for its reversal.

Using closure to show non-regularity

If $L$ is regular, so is $L \cap R$ for every regular $R$. So to prove $L$ not regular, intersect with a regular language and get a known non-regular language.

• $L = \{w \in \{a, b\}^* : \#a(w) = \#b(w)\}$. Then $L \cap a^* b^* = \{a^n b^n\}$ is non-regular, so $L$ is not regular.
• $L = \{0^n 1^m : n \ne m\}$. Its complement, intersected with $0^* 1^*$, is $\{0^n 1^n\}$, so $L$ is not regular.
• $L = \{a^n b^m c^n : n, m \ge 0\}$. Then $L \cap a^* c^* = \{a^n c^n\}$ is non-regular, so $L$ is not regular.

The converse direction: closure also shows languages regular without building a machine (for example a finite union of regular pieces, or $L \setminus F$ for a finite $F$).

What you cannot conclude

• $L_1 \cup L_2$ regular does not imply $L_1$ and $L_2$ regular ($\{a^n b^n\} \cup \overline{\{a^n b^n\}} = \Sigma^*$).
• $L_1$ regular and $L_2$ non-regular: $L_1 \cup L_2$ and $L_1 \cap L_2$ may or may not be regular ($L_1 = \emptyset$ gives $L_1 \cap L_2 = \emptyset$, regular; $L_1 = \Sigma^*$ gives $L_1 \cap L_2 = L_2$, non-regular).
• $L_1 L_2$ regular does not imply $L_1$ and $L_2$ regular: $L_1 = \Sigma^*$ and $L_2$ any language containing $\varepsilon$ gives $L_1 L_2 = \Sigma^*$, however irregular $L_2$ is.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The pumping lemma (pumping lemma) and closure together prove most non-regularity statements; context-free languages are closed under fewer operations (closure of CFLs): they are not closed under intersection or complement.

PYQs

Let L1 and L2 be two languages over a finite alphabet,
such that L1∩L2 and L2 are regular languages. Which of
the following statements is/are always true?

Consider the two lists List I and List II given below:

List 1
List 2
(i) Context free languages

Let Σ = {a, b, c}. For x ∈ Σ* , and α ∈ Σ, let #α(x) denote
the number of occurrences of α in x. Which one or more of
the following option(s) define(s) regular language(s)?

Let L1, L2 be two regular languages and L3 a language
which is not regular. Which of the following statements
is/are always TRUE?

Consider the following statements.
I. If L1 U L2 is regular, then both L1 and L2 must be
regular.
II. The class of regular languages is closed under infinite
union.
Which of the above statements is/are TRUE?

If L is a regular language over Σ = {a,b}, which one of the
following languages is NOT regular?

Consider the DFAs M and N given above. The number of
states in a minimal DFA that accepts the language
 L(M) ∩ L(N) is __________.

Which of the following language is/are regular
languages?

L1 : {wxwR|w,x ε {a, b}* and |w|, |x| > 0}, wR is the
reverse of string w
L2 : {anbm | m != n and m, n >= 0}
L3 : {apbqcr | p, q, r >= 0}

If L1 = {an | n > 0} and L2 = {bn | n >= 0}, consider
(I) L1.L2 is a regular language
(II) L1.L2 = {anbn | n >= 0}
Which one of the following is CORRECT?

Let P be a regular language and Q be a context-free
language such that Q ⊆ P. (For example, let P be the
language represented by the regular expression p*q* and
Q be [pnqn | n ∈ N]). Then which of the following
is ALWAYS regular?

Given below are two finite state automata (-> indicates
the start state and F indicates a final state)
Automaton Y

a
b
→1
1
2
2(F)
2
1

Automaton Z

a
b
→1
2
2
2(F)
1
1
Which of the following represents the product
automaton Z × Y?

Consider the following two finite automata. M1 accepts L1
and M2 accepts L2

Which one of the following is TRUE?

Consider the following finite automata P and Q over the
alphabet {a, b, c}. The start states are indicated by a
double arrow and final states are indicated by a double
circle. Let the languages recognized by them be denoted
by L(P) and L(Q) respectively.

The automata which recognizes the language L(P) ∩
L(Q) is:

Which of the following is TRUE?

Consider the following languages:
L1 = { anwan | w ∈ {a, b}* }
L2 = { wxwr | w, x ∈ {a, b}*, |w|, |x| > 0 }
Note that wr is the reversal of the string w. Which of
the following is/are TRUE?

Self-check

Revision card

References