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).
- The Complement Operation
- Definition
- The complement S^{c} 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
L^{c}.
- L = ^{*}
L^{c} = {}.
- L = {the set of strings of even length}
L^{c} = {the set of strings not of even length}
= {the set of strings of odd length}.
- L = {the set of strings beginning with 01}
L^{c} = {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
L^{c} 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
- 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' = L^{c}, 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.
- 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' = L^{c}, 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.
- 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' = L^{c}, 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)
Table of Contents (up two levels)