This is all serious computer science in this article, but I didn't want you to get upset by the terminology. It's easy to understand what's going on, but it's also easy to get lost in a lot of technical jargon, so I took out the jargon. Here it is if you want to impress your friends with it:
The machines are called `Finite Automata'. `Automata' is Greek; it means `things that go by themselves'. The automata are finite because there are only a finite number of circles and arrows; this is to contrast them with automata that have an infinite amount of memory. `Finite automaton' is a mouthful even for a computer scientist with a Ph.D., so they usually end up abbreviating it to `FA'.
The kind of FA's we've been looking at are called `nondeterministic', or `NFA's for short. This refers to the fact that pennies sometimes get cloned. If there's only one arrow with a particular label leading out of each circle, the pennies never get cloned, and the automaton is called `deterministic' or a `DFA'.
When the FA says `yes', computer scientists say it has `accepted' its input; when it says `no', they say it has `rejected' its input.
The arrows are called `transitions'. Blank arrows are called `
-transitions' . The circles are
called `states'. The start circle is called the `start state'. The
double circles are called `accepting states' or sometimes `final
states'. Computer scientists don't talk about the pennies, because
they are too important to waste time playing with pennies. They just
talk about the `current states', which are the circles that the
pennies would have been sitting on if there were any pennies.
Computer scientists draw the pictures exactly the same way I drew
them for you, except that they don't actually label the start state
with `Start Here'. They do draw that little arrow pointing to it,
however. And they sometimes also label the blank arrows with the
Greek letter so that they can
remember that they're -transitions.
Now you can talk just like a computer scientist.
Return to: Universe of Discourse main page | What's new page | Perl Paraphernalia | How Regexes Work