[Math] What are closure properties of regular languages

automataregular-language

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

Best Answer

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$}}$

Related Question