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.
Exercises
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.
No solutions for this one yet. Hint: Take a DFA \(M\) with 5 or 6 states that accepts some language \(L\). Which states in \(M\) should be made accept states to accept \(\texttt{prefix}(L)\)?
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.
If \(L_1L_2\) is regular and \(L_1\) is finite, then \(L_2\) is regular.
If \(L^R\) is regular, then \(\overline{L}\) is regular.
There are no two NON-regular languages \(L_1,L_2\) such that \(L_1 \cup L_2\) is regular.
No solutions for this one yet. You might need to know a bit more about non-regular languages to answer these
actually.
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.
Since A is regular we know that there exists a DFA \(M_A = (Q_A, \Sigma, \delta_A, q_0, F_A)\) that
accepts it. Next,
we create a new and improved extended transition function \(\delta' : Q \times \Sigma^{*}
\rightarrow Q\). This
transition function is extended because it accepts as input a state \(q \in Q_A\) and a string
\(w \in
\Sigma^*\). As its output, the transition function returns the state \(q'\) that \(M_A\) would be in had
it read \(w\)
starting from \(q\). The goal is to create a machine \(M\) that accepts \(A/B\). If \(y \in A/B\) then
we know that when
we feed \(y\) into \(M_A\) we get to state \(q' = \delta'(q_0, w)\). Once at state \(q'\), we take some
string \(x \in
B\) and feed it to \(M_A\) but now starting from \(q'\). It must be that \(\delta'(q', x) = q_f \in
F_A\) (by definition
of \(A/B\)). Thus the machine \(M = (Q_A, \Sigma, \delta_A, q_0, F)\) accepting \(A/B\) is the same as
the machine
accepting \(A\) except that \begin{align} F = \{ q : \exists x \in B, \delta'(q, x) \in F \}
\end{align}
**NOTE**: It doesn't matter here that \(B\) is not regular. We are not using the fact that a machine
does (or doesn't)
accept \(B\). We are simply using its contents to define a new \(F\), a set of final **states**. All the
computation,
however, is done on \(M_A\) which we know exists. So we aren't using anything that's more "powerful"
than the class of
regular languages.