What are closure properties of regular languages?

Question

In class we've been talking about DFA's and NFA's and being closed under ____. The homework problems say to "use closure properties of regular languages to show that a regular languages are closed under _______." I don't really get what a closure property is, can someone dumb it down? Every example I've looked up shows proofs that (kind of) make sense, but it doesn't clarify what a closure property is. Also, we were explicitly told to use closure properties and not a constructive proof.

An example we did in class was closed under union. It was done as a construction proof ... I think. Let $M_1 = (Q_1, E, d_1, q_1, F_1)$ and $M_2 = (Q_2, E, d_2, F_2)$ s.t. $L(M_1)=A$, $L(M_2)=B$. Build NFA $N=(Q,E,d,q_0,F)$ s.t. $L(N) = A \cup B$, $Q=Q_1 \cup Q_2 \cup \{q_0\}$, $F= F_1 \cup F_2$ and so on assigning values to the 5-tuple definition of the NFA.

Thanks

Answer 1

Let us start with the definition of closure for an operator on a set. If you have an operation $f$ on a set $E$, a subset $S$ of $E$ is closed under $f$ if the result of applying $f$ to the elements of $S$ is still an element of $S$. The operation can be unary (like $f_1(x) = x^2$), binary (like $f_2(x,y) = x+y$), ternary (like $f_3(x, y, z) = xyz$), or $n$-ary for some $n$.

In the case of languages, some common operations are

• Union (binary): $L_1 \cup L_2$
• Intersection (binary): $L_1 \cap L_2$
• Complementation (unary): $L^c$
• Product (binary): $L_1L_2$
• Star (unary): $L^*$

As you know, the set of regular languages is closed under these operations, which means that, if $L, L_1, L_2$ are regular languages, then $L_1 \cup L_2$, $L_1 \cap L_2$, $L^c$, $L_1L_2$ and $L^*$ are also regular.

Now the notion of closure is also used in a larger setting. For instance, in the case of regular languages, let $A$ and $B$ be two alphabets and let $f:A^* \to B^*$ be a monoid homomorphism${}^*$. Then one says that "regular languages are closed under homomorphisms and under inverses of homomorphisms" to mean that:

• if $K$ is a regular language of $A^*$, then $f(K)$ is a regular language of $B^*$,
• if $L$ is a regular language of $B^*$, then $f^{-1}(L)$ is a regular language of $A^*$.

Now, some properties on regular languages can be proved using automata, but some other ones can be proved more easily by using the closure properties listed above or some more advanced closure properties. See this question for an example.

${}^*\scriptsize{\text{that is, a map satisfying $f(1) = 1$ and $f(uv) = f(u)f(v)$ for all words $u$ and $v$}}$

Answer 2

See the following link for an explicit definition of closure properties, and some examples: http://infolab.stanford.edu/~ullman/ialc/spr10/slides/rs2.pdf

Basically, if we say that a set of objects is closed under some operation, we mean that performing the operation on elements of the set produces elements that still lie in the set. In this case, the set (the proper term should be family, not set, but regardless) is that of all regular languages, and the closure property may be the statement "the family of regular languages is closed under union". That means that taking the union of any two regular languages, we still end up with a regular language, which is a very convenient property.

As for proving further closure properties via other closure properties, an example may be best to illustrate:

Regular languages are closed under union, intersection and difference (see the link for proofs). Now, given two sets $A$ and $B$, the operation of symmetric difference is done by computing $(A\cup B)\backslash (A\cap B)$.

If $A$ and $B$ are regular languages, then step by step: $(A\cup B)$ and $(A\cap B)$ are regular, by closure under union and intersection, respectively. Since regular languages are closed under difference, $(A\cup B)\backslash (A\cap B)$ must then also be regular. Since $(A\cup B)\backslash (A\cap B)$ is symmetric difference per definition, we have shown that "regular languages are closed under symmetric difference".