Properties of Regular Languages

Topics

• Purpose

• Our main goal is to identify some basic closure properties of regular languages.

• We will be interested in the following types of closure properties.

• Suppose you give me two arbitrary regular languages L and L'.

• Suppose I perform some kind of operation on L and L' such as the set union operation.

• We want to know if the resulting language L union L' is guaranteed to still be regular.

• If it is, we say the class of regular languages has the property of being closed under the set union operation.

• We will often abbreviate this to say that the class of regular languages is closed under union.

• A second goal is to illustrate the basic methods used to prove such closure properties.

• First, we must define the operation (e.g. set union, set complement) we are interested in.

• We will then create a generic element proof to show that the class of regular languages is closed under the particular operation.

• Key point:

• Note we apply these set operations to individual languages (sets of strings) rather than to language classes (sets of sets).

• However, we are interested in whether or not the resulting language (set of strings) is still a member of a language class (set of sets).

1. The Complement Operation

• Definition

• The complement Sc of a set S is defined to be the set of all elements of the universe U that are not elements of S.

• Note complement is a unary operator; that is, it is a function on a single input.

• In contrast, set union is a binary operator; that is, set union is a function on two inputs.

• Examples of languages L (sets of strings) and their complements Lc.

• L = *
Lc = {}.

• L = {the set of strings of even length}
Lc = {the set of strings not of even length} = {the set of strings of odd length}.

• L = {the set of strings beginning with 01}
Lc = {the set of strings not beginning with 01} = {the set of strings beginning with 00, 10, 11} union {0, 1, }

• Generic element proof that the class of regular languages is closed under complement.

• Observation

• Looking at the proof, we see that a regular language L and its complement Lc are arguably identical in complexity since essentially the same FA can recognize either language.

• This is NOT always the case for other classes of languages, a fact we will see in the next section on context free languages.

• Questions

2. The Union Operation

• Definition

• S union S' of sets S and S' is defined to be the set of all elements of the universe U that are either elements of S or S'.

• Note union is a binary operator; that is, it is a function on two inputs.

• In contrast, set complement is a unary operator; that is, set complement is a function on one input.

• Examples of languages L and L' (sets of strings) and their unions L union L'.

• L = {aab,aaba,aabaa}
L' = {b,aaba,bbb}
L union L' = {aab,aaba,aabaa,b,bbb}

• L is any language
L' = Lc, the complement of L
L union L' = *

• L = {the set of strings beginning with 01}
L' = {the set of strings beginning with 00}
L union L' = {the set of strings beginning with 0 except 0 itself}

• Generic element proof that the class of regular languages is closed under union.

3. The Intersection Operation

• Definition

• S intersection S' of sets S and S' is defined to be the set of all elements of the universe U that are elements of both S and S'.

• Note intersection is a binary operator; that is, it is a function on two inputs.

• Examples of languages L and L' (sets of strings) and their intersection L intersection L'.

• L = {aab,aaba,aabaa}
L' = {b,aaba,bbb}
L intersection L' = {aaba}

• L is any language
L' = Lc, the complement of L
L intersection L' = {}

• L = {the set of strings beginning with 0}
L' = {the set of strings ending with 0}
L intersection L' = {the set of strings beginning with 0 and ending with 0}

• Generic element proof that the class of regular languages is closed under intersection.

4. The Set Difference Operator -

• Definition

• S - S' is defined to be the set of all elements of the universe U that are elements of S but not elements of S'.

• Note set difference is a binary operator; that is, it is a function on two inputs.

• Examples of languages L and L' (sets of strings) and their difference L - L'.

• L = {aab,aaba,aabaa}
L' = {b,aaba,bbb}
L - L' = {aab,aabaa}

• L is any language
L' = Lc, the complement of L
L - L' = L

• L = {the set of strings beginning with 0}
L' = {the set of strings ending with 0}
L - L' = {the set of strings beginning with 0 which do not end with 0}

• Examine the generic element proof that the class of regular languages is closed under intersection and determine how to modify it to show that the class of regular languages is closed under set difference.

• Questions
Regular Languages Chapter (up one level)