[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 union L2 Strings in either L1 or L2
L1 intersection 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
L1superscript R 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.


Copyright 1996 by David Matuszek
Last modified Feb 13, 1996