views:

854

answers:

12

Erm - what the question said. It's something I keep hearing about, but I've not got round to looking into it yet.


(updated) I could look up the definition... but why not (as pointed out by @erikson) get insight into your real experiences and anecdotes. Community Wiki'd incase that helps folks vote up the most insightful answer. Interesting reading so far, thanks!

+1  A: 

Yes! You could look it up!

http://en.wikipedia.org/wiki/Finite_state_machine

Jordan L. Walbesser
It would be more interesting to hear some non-NPOV anecdotes about why a programmer would care about them.
erickson
original research is encouraged!
Jimmy
+10  A: 

Short answer, it is a technique that you can use to express systems with concrete states (as opposed to quantum states / probability distributions).

Quoting the Wikipedia article:

A finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an abstract model of a machine with a primitive internal memory.

So, what does that mean to you? Put simply, it is an effective way to represent the path(s) from a starting state to the end state(s) of the system that you care about. Using regular expressions as a fairly easy to understand example, let's look at the pattern AB*C (imagine that that star is a superscript). I would expect to this pattern to accept strings such as "AC", "ABC", "ABBC", "ABBBC", etc. A at the start, C at the end, some number of B's in the middle (greater than or equal to zero).

If you think about it, it's almost easier to think about this in terms of a picture. Faking it with text (and that my parentheses are a loopback arc), you can see that A (on the left), is the starting state and C (on the right) is the end state on the right.

      _
     ( ) 
A --> B --> C

From FSAs, you can continue your journey into computational complexity by heading over to the land of Turing Machines.

However, you can also use state machines to represent real behaviors and systems. In my world, we use them to model certain workflow of actual people working with components that are extremely intolerant of mistakes in state order. As in, "A had better happen before C or there will be a very serious problem. Make that be not possible right now."

Bob Cross
I love the ascii-art FSM.
rascher
Thanks - I couldn't think of another way to draw the picture without being all "pretentious Visio" at people.
Bob Cross
+2  A: 

Every programmer should know about them because they are an excellent tool for certain kinds of problems, where the usual 'iterative-thinking' approach would yield nasty, complex code.

A typical example is game AI, where NPCs have different states that change according to where the player is, something like:

  • NPC_STATE_IDLE
  • NPC_STATE_ALERT (player at less than 100 meters)
  • NPC_STATE_ENGAGE (player attacked NPC)
  • NPC_STATE_FLEE (low on health)

where a FSM can describe easily the transitions and help perform complex reasoning about the system the FSM is describing.

Vinko Vrsalovic
+9  A: 
Charlie Martin
Formally, huh? :-) I've been dope-slapped pretty good for being formal when talking to programmers. Cheers.
Mike Dunlavey
Don't get me started, Mike. I don't know how often I've been asked "does it always have to be like a math problem?" The only answer is to say "Yes. Computer science is a mathematical subject."
Charlie Martin
Yes, although sometimes I think the way different languages have their adherents is almost like musical genres.
Mike Dunlavey
Yeah, you know, I don't think the cognitive connection between music and programming has ever been explored enough. On the other hand, I think the languages questions may be more like theology.
Charlie Martin
adolescent theology, at that...
Mike Dunlavey
Speaking of FSA, you might be interested in this paper I wrote in '98. http://arxiv.org/PS_cache/quant-ph/pdf/9807/9807026v1.pdf It was motivated by trying to find a better way to prove software correct.
Mike Dunlavey
+1  A: 

What it is is better answered on other sites (such as Wikipedia), because there are pretty extensive answers out there already.

Why you should know them: Because you probably implemented them already.

Any time your code has a limited number of possible states (that's the "finite state" part) and switches to another one once some input/event happend (that's the "machine" part) you've written a finite state machine.

It is a very common tool and knowing the theoretical basics for that, being able to reason about it and knowing how to combine two FSMs into a single one that does the same work can be a great help.

Joachim Sauer
+2  A: 

You need state machines whenever you have to release your thread before you have completed your operation.

Since web services are often not statefull, you don't usually see this in web services--you re-arrange your URL so that each URL corresponds to a single path through the code.

I guess another way to think about it could be that every web server is a FSM where the state information is kept in the URL.

You often see it when processing input. You have to release your thread before the input has all been completed, so you set a flag saying "input in progress" or something like that. When done you set the flag to "awaiting input". That flag is your state monitor.

More often than not, a FSM is implemented as a switch statement that switches on a variable. Each case is a different state. At the end of the case, you may set the state to a new value. You've almost certainly seen this somewhere.

The nice thing about a FSM is that you can make the state a part of your data rather than your code. Imagine that you need to fill out 1000 items in the database. The incoming data will address one of the 1000 items, but you generally don't have enough data to complete the operation.

Without an FSM you might have hundreds of threads waiting around for the rest of the data so they can complete processing and write the results to the DB. With a FSM, you write the state to the DB, then exit your thread. Next time you can check the incoming data, read the state from the thread and that should give you enough info to determine what code to run.

Nearly every FSM operation COULD be done by dedicating a thread to it, but probably not as well (The complexity multiplies based on number of states, whereas with a state machine the rise in complexity is more linear). Also, there are some conceptual design issues--examining your code at the state level is in some cases much easier than examining it at the line of code level.

Bill K
+2  A: 

in OOP terms: if you have an object with methods that you call on certain events, and some (other) methods that have different behaviour depending on the previous calls.... surprise! you have a state machine!

now, if you know the theory, you don't have to rethink it all. you simply say: "piece of cake, it's just a state machine" and go on to implement it.

if you don't know the theory you'll think about it for a while, write some clever hacks, and get something that's difficult to explain and document... because you don't have the words to describe it

Javier
I especially like the last sentence.
Mike Dunlavey
+1  A: 

FSAs are great data structures to understand because any chance you have to implement them, you're working at the lowest level of computational complexity on the Chomsky hierarchy. A great example is in word morphology (how parts of words come together). A lot of work has been done to show that even the most severe cases can be analyzed in this extremely fast analytical framework. Take a look at Karttunnen and Beesley's work out of PARC.

FSAs are also a great place to start learning about machine learning concepts like hidden markov models, because in many ways, the problem can be broken down using the same ideas and vocabulary.

Robert Elwell
+2  A: 

Good answers above. I would only add that FSA are primarily a thinking tool, not a programming technique. What makes them useful is they have nice properties, and anything that acts like one has those properties. If you can think of something as an FSA, there are many ways you can build it:

  • as a regular expression

  • as a state-transition table

  • as a while-switch-on-state loop

  • as a goto-net (horrors!)

  • as simple structured program code

etc. etc.

If somebody says something is a FSA, you can immediately know what they are talking about, no matter how it is built.

Mike Dunlavey
+1  A: 

One item that hasn't been mentioned so far is the semantic equivalence of finite state automata and regular expressions. A regular expression can be compiled to a finite state automaton (this is how regex libraries work) and vice-versa.

ConcernedOfTunbridgeWells
+2  A: 

Important: If you are a "visual" style learner, stop everything you are doing and go to this link ... Right Now.

If you are a "visual" learner, here is an excellent link that gives a very accessible introduction.

Reanimator by Oliver Steele

It looks like you've already approved an answer, but if you appreciate "visual" introduction to new concepts, as is common, you really should check out the link. It is simply outstanding.

(Note: the link points to a discussion of DFA and NDFA in the context ofregular expressions -- with animated interactive diagrams)

dreftymac
+1  A: 

FSA (including DFA and NFA) are very important for computer science and they are use in many fields including many fields. For instance hidden markov fields for speech recognition also regular expressions are converted to the FSA's before they are interpreted by the software and NLP (Natural Language Processing), AI (game programming), Robot Programming etc.

One of the disadvantage of FSA's are they are usually slow and usually hard to implement and hard to understand or visualize while reading the code, but they are good because they usually provide generic solutions to the problems and they are well-known with a lot of studies on FSA's.

systemsfault