Overview of Closure

• What is "Closure" and what does "Closed Under" mean?
• How does Closure relate to Regular Languages and Context-Free Languages? (i.e. What do I need to know about Closure for this class??)

What is "Closure" and what does "Closed Under" mean?

Example 1: The set "Candy"

Lets take the set "Candy." So members of the set are individual pieces of candy. If you take a piece of candy, and drop it on the ground, is it still candy? I say, according to the 5-second rule, I would still eat it, so it's still candy. That means that our set Candy is closed under the operation "drop."

What if I take two pieces of candy, x and y, and stick them together--stick(x,y)--to make a new piece of candy. Since what comes out of stick(x.y) is a piece of candy, Candy is closed under stick. Note: it only works if both operands are candy.

Now let's say that I take a piece of candy, x, and feed it to a bird. Then later, after digesting the candy, the bird leaves some droppings on my car (assume the droppings came from the candy, and we'll call this bird(x)). Is bird(x) candy? No way. So Candy is not closed under bird.

An important part of closure is that when we say that the set is "closed under" an operation, it has to be true for everything in the set. So even if all kinds of candies--except for one--were still candy after the bird() operation, Candy would still not be closed under bird(). Next is an example of closure that is more formal.

Example 2: The set of Integers

Can you think of some operations that the integers are closed under? One is addition. But the integers are not closed under division. It works sometimes--for example 12/3 = 4 (all integers)--but remember that it has to work all the time.

How does Closure relate to Regular Languages and Context-Free Languages? (What do I need to know about Closure for this class??)

1. You need to memorize certain fundamental operations that the set of Regular Languages and the set of Context-Free Languages are closed under. These are called the "closure properties" of that set. See chart below.
2. Problem type 1: you are given some operation and you need to prove that the set of languages (either regular languages or context-free languages) is closed under that operation "from scratch" by construction.
   • This page tells you how to do that for regular languages.
   • For context-free languages, follow the same template as for regular languages, but use grammars or PDA's, instead of DFA's and NFA's.
3. Problem type 2: you are given some operation and you need to prove that the set of languages (either regular languages or context-free languages) is closed under that operation by using the closure properties for that set (that you memorized). This is a "shortcut" way to do (2).
   • This page tells you how to do it for regular languages.
   • For context-free languages, follow the same template as for regular languages, but use the closure properties for context-free languages (i.e. you can't use complement and intersection).