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?