Listing 1.
Terminology
Mark-Jason Dominus

How Regexes Work
The Perl Journal, Spring 1998
 

This is all serious computer science in this article, but I didn't want to get bogged down 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:

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, 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 'epsilon 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 as I drew them for you, except that they don't actually label the start state with 'start'. They do draw that little arrow pointing to it, however. Oh, and they sometimes also label the blank arrows with e so that they can remember that they're e-transitions.

Now you can talk just like a computer scientist.