This section will be about closure properties of regular languages i.e., understanding under which operations regular languages are closed. You can find the notes related to this section here.

What do we mean by closure properties of regular languages?

What do I actually mean by closure properties of regular languages? If I have a regular language \(L\) and apply some operation \(\texttt{op}\) to it, how can I prove that \(\texttt{op}(L)\) remains regular (if this is actually true)? What about for binary operations like the union and the concatenation? Do these language operations always preserve regularity or are there cases for which taking the union of two regular languages can create a non-regular language (it’s OK if you don’t know what a non-regular language looks like at this point). The “preservation of regularity” is what I mean by closure properties which I discuss in the following video. I also present the general motivation of closure properties and how to prove that regular languages are closed under certain operations.

Examples of closure property proofs

There are some “classic” closure property proofs that I am “obligated” to discuss here for completeness. I start by giving an in-depth proof for the union operation and slowly convert most of the proofs to sketches for simplicity.

  • Regular languages are closed under the union.
  • Regular languages are closed under language concatenation.
  • Regular languages are closed under the \(L^*\) operation.
  • Regular languages are closed under the complement.

Closure property proofs may at first seem more difficult than simply creating DFAs or NFAs to accept languages. That’s probably because they are! But they are also a lot more fun once you get the hang of general flow of the proof. See the exercises for additional practice.

Using closure properties to prove that languages are regular

If you recognize that a language \(L\) consists of sub-languages which are combined together via language operations (e.g. the union, intersection), then closure properties tell us that if each of these sub-languages are regular that \(L\) is also regular. Therefore, there may be situations where direct complicated proofs (constructing a DFA or an NFA) can be substituted with the use of closure properties. More in the next video.


Exercise. Prove that if \(L\) is regular then \(L^R = \{w^R : w \in L\}\) is also regular.

Exercise. Prove that if \(L\) is regular then \(\texttt{prefix}(L) = \{x \in \Sigma^* : \exists y \in \Sigma^*, xy \in L\}\) is also regular.

Exercise. Let \(L_1, L_2\) be two regular languages over \(\Sigma=\{a, b\}\). Prove that \(\texttt{shuffle}(L_1, L_2)\) is regular where \(\texttt{shuffle}(L_1, L_2) = \{x_1y_1x_2y_2 \dots x_ky_k : x_1x_2\dots x_k \in L_1, y_1y_2\dots y_k \in L_2, x_i, y_i \in \Sigma\}\).

Exercise. Given \(L_1 = \{ab^na: n > 0\}\), \(L_2 = \{ba, bba\}\), \(L_3 = \{aw : w \in \{a,b\}^* \}\). Is \(L_1 \cdot L_2 \cup L_3\) regular?

Exercise. Is \(L = \{a^nb^n: n < 42\}\) regular? Prove your answer. (A nice, more general result follows from the answer to this question!)

Exercise. If \(L\) is a regular language, show that language \(\texttt{append1}(L) = \{ x1 : x \in L \}\) is also regular. \(\Sigma = \{0,1\}\). Is the proof the same for the operation \(\texttt{cutout1}(L) = \{ x : x1 \in L \}\)?

Exercise. Prove or disprove the following statements.
  1. If \(L_1L_2\) is regular and \(L_1\) is finite, then \(L_2\) is regular.
  2. If \(L^R\) is regular, then \(\overline{L}\) is regular.
  3. There are no two NON-regular languages \(L_1,L_2\) such that \(L_1 \cup L_2\) is regular.

Exercise. (Sipser 1.35) Let \(A/B = \{ w : wx \in A \text{ for some } x \in B \}\). Show that if \(A\) is regular and \(B\) is any language, then \(A/B\) is regular.