Class 4: Set Theory Basics


Reading
Sections 1.4 of Theory of Computing, A Gentle Introduction ... again.
Homework
To properly read view this homework, use the latest version of the Mozilla browser [download Mozilla], or Firefox, or the latest Netscape, or Opera or (if you have a Mac) Safari ... pretty much just not Explorer. Why? Well the HTML 4.0 specification includes a list of "character entities" for mathematical operators include "element of" (∈), "is not an element of" (∉), and "subset of" (⊆). Internet Explorer 6.0 does not implement all of these, including some important ones for this course. So use another browser, like mozilla, that does.
  1. Fill in true or false:
    x ∈ {w,x,y,z}T/F?
    w ∈ {(w,x),(y,z),(w,z)}T/F?
    y ∈ {{w,x},{y},{z}}T/F?
    (x,y) ∈ {(w,x),(y,x),(z,x)}T/F?
  2. Explcitly write down all the elements of the set {Q,A}x{0,3,5}:
  3. Fill in true or false:
    {} ⊆ {w,x,y,z}T/F?
    {(y,z),(w,z)} ⊆ {(w,x),(y,z),(w,z)}T/F?
    {y} ⊆ {{w,x},{y},{z}}T/F?
    {{y}} ⊆ {{w,x},{y},{z}}T/F?
  4. Write the cartesian product expression that defines the set:
    {(cat,X),(dog,X),(cat,Y),(dog,Y),(cat,A),(dog,A)}
  5. Suppose Q1 = {q0,q1,q2} is the set of states for a machine M1, and Q2 = {p0,p1,p2,p3} is the set of states for a machine M2, and suppose that following our algorithm we create a machine M3 accepting the intersection of the languages accpeted by M1 and M2. Write down a nice concise expression (not in english) for the set of states of M3.

Describing a finite automaton as a string of symbols
Suppose you wanted to describe a finite automaton to someone over the phone. So you're looking at the diagram, but you can't show them the picture you have to describe it in words, and describe it well enough that they'll be able to draw it correctly for themselves. (Note: In class we'll try this!) What would you tell them? Hopefully this excercise will convince you that if we want to specify a finite automaton we need to know the following pieces of information: This is the information we need to communicate, but what language will we use? We'll use the language of sets from mathematics.

In what follows, we'll be developing enough knowledge of sets and functions to describe the following machine M1:

Note: Of course JFLAP is able to "Save" your finite automaton specifications, so it must have some way of converting these diagrams into strings of symbols. It does this using "XML". For instance, JFLAP saves the above diagram as M1.jff which, if you look at it, you can pretty much reason out for yourself. Notice that JFLAP saves xy-coordinates of states. This is a property of a diagram, not of the machine itself, so we're not interested in putting that kind of information into our mathematical definition of a machine. Also, it is possible to store "incorrect" definitions --- for instance if no state is marked initial. This makes sense for JFLAP, because you might save a machine that you're not yet finished constructing in order to work on it later. For our mathematical definition, however, we want to ensure that any string of symbols that matches our specification defines a legal machine.

Sets
You guys learned all about sets in discrete math, but here's a little review in case you've forgotten some things. Hopefully, however, you're all pretty clear on writing down sets, what the elements of a set are, and what subsets of a set are. We'll go over some simple sets and listing their elements and their subsets.
Let's try writing as much of the above machine as we can using what we know about sets.
Tuples and Cartesian product
You're all familiar with an ordered pair, like (a,3). The main feature of an ordered pair is that the order matters! For example, (a,3) ≠ (3,a). Why? Because the order is different. Ordered pairs like this are examples of tuples, they're 2-tuples to be precise, even though just plain "tuple" usually means 2-tuple. Of course, we could add more slots to form 3-tuples like (a,3,b), or 4-tuples like (3,4,x,y), and so on. Our description of a finite automaton will be a 5-tuple:

(

{q0,q1,q2},

{a,b},

???,

q0,

{q0,q2}

)

statesalphabettransitionsstart
state
accepting
states
A 5-tuple representing M1 (to the extent we can at this point)

Tuples play much the same role in mathematics as classes or structs do in C/C++: You use them to package several pieces of information together as a single object. The big difference is that the componants of a tuple are not named, rather you simply refer to the 1st componant, 2nd componant, etc. A tuple itself is like an instance of a class. For example, with a simple class for representing points we have the following:

ClassExample Instances
class Point   
{
public:
  double x,y;           
};
1.5 0.2
xy
or
-0.1 2.7
xy
or
-3.0 0.0
xy

The instances in the above example correspond to tuples (1.5,0.2), (-0.1,2.7) and (-3.0,0.0). In general, tuples are like instances of a class, but what takes on the role of the class definition? A class definition is simply a specification of what an instance can be. To specify what a tuple "can be", in other words to specify what values can appear in each componant, we use the cartesian product, which we denote with an x. Remembering that R stands for the real numbers, RxR denotes the set of all tuples whose first componant is a real number and second componant is also a real number. We can do the same things with any set we like:

So, we have the cartesian product to define sets of tuples like a class definition defines the set of all possible instances. However, we actually have more control with these mathematical constructs than we get with class definitions For example, suppose we wanted a structure about free periods in a Mid's academic schedule. The possible days you might have a period free are M, T, W, R, F. The possible periods are 1, 2, 3, 4, 5, 6. Here's the class definition and tuple-set definition you would use in defining a "Free Period":

class definitiontuple-set definition
class FreePer       
{
public:
  char d;
  int p;
};
FP = {M,T,W,R,F} x {1,2,3,4,5,6}

Now, with the class definition all sorts of crazy things are allowed, like the "free period" d = 'Q', p = -12. With the tuple-set definition, you only get the real "free periods".


Christopher W Brown
Last modified: Tue Nov 22 12:00:50 EST 2005