Fog Creek Software
Discussion Board




Real World Metaphore

In a continued effort to explain what I do to my dear spouse, I'm looking for a good metaphor to explain the concept of finite state machines.

I'm currently writing a FSM implementation of an XML parsing engine (for a relatively new programming language that doesn't yet have a native XML parser. Also, projects like xerces are way too big for my needs). I think it's an interesting project, and I've been telling my wife little bits and pieces of why I'm doing it, but when she asks "what is a finite state machine" I'm at a loss for an easy way to explain it.

It's easy to explain a stack because you can refer to the salad-bar-plate-stackers. And it's easy to explain a queue becuase it's exactly like the way we line up for tickets at the movies. And it's even possible to explain the structure of an XML document, because I can show an example document with for a bookstore with <book> and <author> and <title> tags.

But I'm having a hard time thinking of a good real-world example that I can use to explain how a finite state machine works (and why you'd want to use one).

For some reason, it seems like the perfect example just at the tip of my brain, but I can't quite find it. I want to say "a telephone is kind of lika a FSM" or "a tv set is kind of like a FSM" but they aren't.

Any ideas?

Benji Smith
Thursday, March 13, 2003

How about a soda machine?  Each coin/control moves it to a different state, generates output, etc.

just guessing
Thursday, March 13, 2003

model train set?

Joel Spolsky
Thursday, March 13, 2003

Board Game?

Matt Kennedy
Thursday, March 13, 2003

I saw an explanation somewhere that used an automatic transmission as an example...

Martha
Thursday, March 13, 2003

What about a garage door with the input coming from the garage opener?  That's how I learned about FSMs at college.

Marcos M. Rubinelli
Thursday, March 13, 2003

Etch-O-Sketch?

B#
Thursday, March 13, 2003

BURMA!!!!

Oh sorry - I panicked.

Philo

Philo
Thursday, March 13, 2003

How about a magic house of rooms. Each room has many doors, all one way. Every door has a light above it.
When the light goes on (an event) you go through the door (state transition) into a new room (state).
It is magic because you can go through a door and be back in the same room.
You can extend the metaphore by claiming that each room has a machine that lets you do one and only one thing.
By moving through all of the rooms, you get work done.
No hallways ;-)

Doug Withau
Thursday, March 13, 2003

Elevators?

States;

- FloorX, if it is available and on a given floor (X)

- Out of service (with an optional floor modifier)

- Reserved for movers (again with an optional floor modifier)

Further, if required;

- On the correct floor, and available, but doors are closed

You can make it as simple or complex as you want.

For further credit, the reader may explain the difference between Mealy and Moore machines using the button and floor lights ;-)

Shrinky
Thursday, March 13, 2003

I'm just going to be a pain here. Why are telephones and tv's not state machines?

Phone is off. State 1.
Turn phone on. State 2.
Press a number. State 3a.
Press six more numbers. States 3b through 3g.
Pressing the power key (cordless) returns to state 1.

Perhaps anytime an object looks, acts, feels, or smells different than it did yesterday, there's an FSM lurking in the shadows? I'm thinking of an FSM involving personal hygiene and showering, but that's best left for another time.

Thanks guys, now I can't stop thinking about this. Decidious trees? Venetian blinds? My pen & pen cap?

Oooops, now I'm late to go home, so moving to the 'Late to pick up girlfriend' state, my internal Mealy machine reveals that a move to that state requires that I press the 'Post Message' butt<end of signal>

Finally Stopped Monologue
Thursday, March 13, 2003

Washing machine?

UI Designer
Thursday, March 13, 2003

What's a finite state machine?


...sorry, someone had to make it their reply, so I decided to be the one ;)

Brian Hall
Thursday, March 13, 2003

Traffic lights?

Simple state changes are juat the lights changing colours.

Throw in a pedestrian crossing where the pedestrians have to press a button to make the lights change and you've got My First FSM.

Tom Payne
Thursday, March 13, 2003

Good replies.

I've thought through several of them before but none of them have quite satisfied me, since one of the most important aspects of a FSM (at least, as far as I've always thought) is the fact that the states are controlled by the system itself, rather than by an external actor.

A train set, for example, seems to fall short because the train just zings around on a predefined series of tracks. Even if there are switches and track junctures, the train doesn't take them because the train has no mechanism of flipping the switches itself. An external actor has to flip the switches to change the layout of the track. And even if you have an external actor (someone playing with the trainset), that actor still needs to operate on a set of criteria that can be used to decide when to flip the switches.

Telephones and soda machines both make sense to me as FSMs, but the differentiation between the different states may be a little too obscure to explain to a non-technical person as different states.

Oddly enough, my favorite example so far is the "person wandering around in a house with magic doors" example. Even though it's certainly not a real-world example, it illustrates the idea really really well.

Also, a stoplight doesn't quite do it for me, but a "stoplight with cars and a pedestrian" is good.

Keep em coming. This is fun.

Benji Smith
Thursday, March 13, 2003

What about a turnstile? Those things where you have to drop money into before you can pass to get into the subway?

1. The initial state is locked.
2. When a token is placed into the turnstile, it is then unlocked.
3. After the person passes through the turnstile, it is then locked.
4. If the person pressed the ticket button before passing through the turnstile, then a ticket is printed after the person passes through the turnstile.

HeyMacarana
Thursday, March 13, 2003

I was explained FSMs in Uni using the vending machine analogy, I found it easy to understand. I guess that the fact that I still remember the theory behind FSMs some 20+ years later proves the analogy to be effective.

If you have trouble explaining an FSM without being explicit about how FSMs are implemented (by a computer program, electronic vending machine or whatever other means) then use graphical representations of abstract concepts. Draw simple graphs, define nodes as states, say things like "so when I pop 25 cents into the coin slot, this is what happens", draw state transitions. Start with a very simple vending machine, one in which all items cost 2 euros and doesn't give change if you put 7 in. If the state machine is simple it will be easier to represent graphically, easier to understand and therefore the analogy will be more effective.

FSMs are nothing but an _abstraction_, since FSMs are abstract concepts it's very unlikely that you'll find some particular mundane object that embodies a FSM, so analogies are just as good as you can make them be.

Methinks...

Beka Pantone
Thursday, March 13, 2003

Did anyone else read those "choose your own adventure" books as a child?

For example:

As you sneak into the room, a big horrible zombie lumbers out of the closet.  Do you...
... bash the zombie on the head (turn to page 17)
... run screaming (turn to page 42)

The formula is something like:
- Get input (a big horrible zombie)
- Make decision (run or fight?)
- Change state (goto page 17)
- Generate output (page 17: the zombie had two heads so it gobbles you up!)

This seems quite FSM-like to me.

Lurker
Thursday, March 13, 2003

Oh dear the radio's exploded...

penguin
Thursday, March 13, 2003

I once programmed a Survivor paradoy tournament. The concept was really simple, there were 16 contestants, they come on in pairs and gave reasons you should spare them. Then a shotgun appeared and you shot one. The winner moved to level two, which had eight 'survivors'. They sometime refered to each other, hit each other, etc so the animation would change slightly for things like 'he or she', black eyes, clothes etc.

I thought it would be really easy to brute force method, but it was crazily hard! Then between that project and the sequel I learned about state machines... bingo! The sequal too about a day instead of two weeks.

So things like tournaments. When you hear the announcers saying 'if the Packers win and the Rams lose, the Titans will play Dallas at home', that is an easy to understand state machine at work. Of course if your wife is like my wife, explaining with a football metaphor might not make it easier : ).

Robin Debreuil
Friday, March 14, 2003

I always think of a finite state machine as being like induction day at college.

At my college/university you had a big hall full of tables.  Each table had a person with a box full of cards and stuff.

Before you could do anything else you needed an ID card  so you went to the ID card table and they gave you an ID.

They you could go and collect the keys to your room, or enrol on a course.

Each table is like a state, and when at that table you are dealing with specific task.

Some tables require you to have already visited another table (such as needing you ID card)

I think this example also shows the benefits of using FSM.  Trying to handle everything at once would be a nightmare  especially when youve just moved away from home.  Thankfully, you only need to worry about one table at a time and the options for you next action are always clear.

Ged Byrne
Friday, March 14, 2003

I'd use cooking as an example of an FSM.  First your in the "what's on hand" state.  Then move to "find recipe".  Following are "accumulate ingrediants", "prep", "suate veggies", "brown meat", "add meat to veggies".  You can add stuff like "not enough chicken, return to find recipe state".

I knew all that cooking I did would come in handy someday :)

jharkins
Friday, March 14, 2003

How about one of those programmable car radios.  Each time you press a button, it goes to a new state.  If you like to talk about hierarchical state machines, you can toss in the band selection button.  If the band tuner is set to AM, it's one group of states, FM is another group, and FM2 is a third group.

anon
Friday, March 14, 2003

...or how about having her explain why she would say yes to a question when she was happy, and no to the same question when she wasn't? Is it the same person? We even call that 'emotional state'.

Probably easier to relate to than football anyway.

Robin Debreuil
Friday, March 14, 2003

*  Recent Topics

*  Fog Creek Home