Sections 1.4 of Theory of Computing, A Gentle Introduction ... again.
Homework
Printout the homework and answer the questions on that paper.

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:
• the states
• the alphabet
• the transitions
• the start state
• the accepting states
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/are-learning 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.
• the states - What we really want here is the set of states: {q0,q1,q2} in this case.
• the alphabet - An alphabet is a set of characters: {a,b} in this case.
• the transitions - This we still don't know how to do, because it's not as simple as a set or element or subset.
• the start state - This must be an element of the set of states: q0 in this case.
• the accepting states - Since more than one state may be accepting, we can't give a single element of the set of states, we need a subset of the set of states: {q0,q2} in this case.

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:

$M1 = \left( \underbrace{\{q_0,q_1,q_2\}}_{\text{states}}, \underbrace{\{a,b\}}_{\text{alphabet}}, \underbrace{???}_{\text{transitions}}, \underbrace{q_0}_{\text{start state}}, \underbrace{\{q_0,q_2\}}_{\text{accepting states}} \right)$ 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 Java/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 x y
or
 -0.1 2.7 x y
or
 -3.0 0.0 x y

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:

• Example: if S1 = {0,1} and S2 = {a,b,c} then S1xS2 = {(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)}
• Example: if S1 = {0,1} and S2 = {i,j} then S1xS2xS1 = {(0,i,0), (0,i,1), (0,j,0), (0,j,1), (1,i,0), (1,i,1), (1,j,0), (1,j,1)}
• Example: if S1 = {0,1} and N denotes the non-negative integers then S1xN = {(0,0), (1,0), (0,1), (1,1), (0,2), (1,2), (0,3), ...}

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}

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: Fri Aug 28 16:13:52 EDT 2009