Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am considering giving a presentation to middle schoolers, aged about ten to fourteen, about finite automata and regular languages.

Average American students have no problem with uses of the concepts of states and transitions such as modeling real world activities and designing electronic devices.

Regular languages (and regular expressions) are a little more advanced. Such students are certainly able to manipulate and use them, but a certain level of computer literacy is needed to see their usefulness, for example in searching through text.

Let's assume that the students can deal with all of that. The theoretical significance of the equivalence in power of the two models still seems a bit out of reach. So I am looking for a way to connect the two that will be accessible.

The difficulty is that for the canonical examples, the two models involve independent concerns.

Examples of finite automata include control of a machine with a finite set of inputs, like a vending machine with coins and buttons. Excellent student participation activities are at MathmaniaCS (UIUC) and CS Unplugged (look at them all but these are just about FSMs).

Examples of regular expressions include describing words from a language, like finding patterns in a text. For a finite automaton, the goal is to figure out what finite sequences of actions get to a certain state, for example, what combinations of change get to the right amount. For a regular expression, the goal is to match a pattern, usually infinite in possibility. The corresponding regular expression for the interesting question in a finite automata setting is really pretty uninteresting.

For example, one finite state machine activity that is fun is a treasure hunt, going from island to island (the states) using a secret code (the transitions). However, the language of the code to get to the treasure is boring: a single word in the language.

For an interesting language question in finite automata, one would like to ask for a non-trivial regular expression that is the description of a non-trivial solution to some path in the finite automaton.

My question is (finally): what is a good example of a non-trivial regular expression that, for some finite automaton (hopefully with real world connections), gets you from one state to another?

share|improve this question
For a finite automaton, the transitions are always of length 1 (of course you can generalize the model, but that doesn't give you anything). However, you could still play your game with islands, i.e. the passphrase would take you through different islands and the objective is to reach the treasure island (the accepting state). Another idea might by with synchronizing words: you don't know where you are, and you need to get to particular place. –  dtldarek Mar 9 '12 at 21:24
add comment

1 Answer

I know of a few examples:

(1) Scrabble dictionary: you can use a finite automaton to accept a few English words. See Figure 2 in A. Appel and G. Jacobson, The world’s fastest Scrabble program, Commun. ACM 31, 572–578, 585 (1988). Actually, this technique works very well in practice.

(2) Numerical codes, passwords. You can construct a small automaton that accepts your credit card number, but rejects the other ones.

(3) Pattern matching (a variant of the previous one): you can write a small automaton that searches for occurrences of a given word, like dog.

(4) River crossing puzzles like the fox, goose and bag of beans puzzle, can be represented by a finite automaton.

(5) Freight elevators with two buttons, up and down.

(6) A turnstile. See Wikipedia

(7) Various computations in binary (more advanced).

share|improve this answer
Yes, these are all good examples of uses of finite automata either in design or analysis of engineering systems, but does their interpretation as regular languages add anything meaningful? Well, Kleene closure really needs to be used meaningfully. –  Mitch Aug 16 '13 at 22:02
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.