Where Are We?
Really, where are we here? Lost already in the woods? Can't see the forest for the trees?
Hey, don't worry. Suck it up. We can do this. And, like all exciting adventures, we'll have fun doing it (or die trying).
Where We Came From
Before we jump headfirst into this jungle of odd botanical delights and dangerous animal species bearing names like automata, regular expressions, languages, and grammars, let's remember what we are up to. This should help orient us.
We are, you will recall, attempting to chart our our chosen academic field of computer science, and we are now embarking in earnest on our journey. Before we started we laid a foundation that helps us know how to proceed. We'll review the key points here.
- Computer Science is the study of problems and their solutions.
- To qualify as a candidate for study in Computer Science, a problem must
- be well defined (otherwise we could not agree on a solution)
- have an infinite number of instances (otherwise we could compute the answers for each of the finite instances of the problem once and for all, store those answers in a table, and just look up the answers to any one of the instances as needed, and where's the fun in that?)
- Any proposed solution to a problem under study must likewise
- be finite (otherwise we could scarcely call it a solution, as in our real world of computer science, we cannot construct objects that are infinite)
- provide a means of computing the correct answer for any of the infinite instances of the problem in a finite amount of time (otherwise, it hasn't solved the problem).
And so, we get to the crux of our quest. What constitutes a solution? Early computer scientists who contemplated this question came to this agreement:
- If a machine could be built that, when provided with any instance of the selected problem as input, computed the correct answer for that input instance in a finite amount of time, that machine would be declared to be a solution to the problem.
Finally, in order to make our lives easier along the journey, we have largely restricted our quest to the study of
- decision problems (problems that have "yes" or "no" answers to every problem instance) and their solutions.
These machines that solve problems are not really computers as we know them today. For one thing, a new machine must be designed for each different problem: one machine only solves one problem. Furthermore, we are really talking here about machine designs, not real machines. Thus, the designs must be simple enough that everyone would agree that said machines could be built if we wanted to do it. Or, put another way, the designs are simple enough that virtually anyone could carry out the steps by hand that the machine would perform and arrive a the same answer that the machine would produce.
Where We're Going
That's where we came from. Where are we going? We are going to find some of these machines that solve problems. More specifically, we are going to find certain classes of machines that all are built the same way and study these different classes. What kinds of problems can machines of a given class solve? What kinds of problems can they not solve? In this chapter we are going to look at a class of machines known variously as
- finite state machines
- finite automata
- finite state automata
Different traditional textbooks you might encounter will use one or the other of these names. They all mean the same thing. We will use the term finite state automaton in this book.
Moving Out
Now that we have oriented ourselves, let's move out!.
