[Overview] [Previous] [Next]

# Closure I

A set is closed under an operation if, whenever the operation is applied to members of the set, the result is also a member of the set.

For example, the set of integers is closed under addition, because x+y is an integer whenever x and y are integers. However, integers are not closed under division: if x and y are integers, x/y may or may not be an integer.

We have defined several operations on languages:
 L1 L2 Strings in either L1 or L2 L1 L2 Strings in both L1 and L2 L1L2 Strings composed of one string from L1 followed by one string from L2 -L1 All strings (over the same alphabet) not in L1 L1* Zero or more strings from L1 concatenated together L1 - L2 Strings in L1 that are not in L2 L1 Strings in L1, reversed
We will show that the set of regular languages is closed under each of these operations. We will also define the operations of "homomorphism" and "right quotient" and show that the set of regular languages is also closed under these operations.