# Connecting finite automata and regular languages in teaching/applications

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?

-
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

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).

-
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

(The question is dated, but seeing a list of applications of more complex regular expressions may help someone, someday.)

Some examples of possible applications of non-trivial regular expressions (using Kleene closure) are:

• A vending machine (that has no limit to how much money it accepts). This is interesting because of the variety of bills and coins that can be accepted.
• Typing an email. The complexity could be high if backspace and formatting is allowed.
• A voting location. People queue up, check in, move to an open voting booth, cast a vote, and check out. This is another scenario that could be quite complex depending on the allowed transitions.
• A vehicle counter that counts cars as they pass by. (Press button to start/stop counting.)
• A cash register. Tally purchases.
• A gas pump. Record gas dispensed.

All of the above will tally, count, or otherwise store up the input. The states of interest are: Start Accepting Data --> Accept Data --> Stop Accepting Data

The examples ignore the fact that most physical devices will fail or otherwise reset if the input string is too long.

-