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? |
{} ⊆ {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? |
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.
( | {q0,q1,q2}, | {a,b}, | ???, | q0, | {q0,q2} | ) |
states | alphabet | transitions | start state | accepting states |
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:
Class | Example Instances | |||||||||||||||||||
class Point { public: double x,y; }; |
| or |
| or |
|
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 definition | tuple-set definition |
class FreePer { public: char d; int p; }; |
FP = {M,T,W,R,F} x {1,2,3,4,5,6} |
d = 'Q', p =
-12
. With the tuple-set definition, you only get
the real "free
periods".