Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm looking for good examples of finite state machines, language isn't particularly important, just good examples.

Code implementations are useful (generalized pseudo-code), but it's also very useful to gather the various uses of FSM's.

Examples don't necessarily need to be computer based, for example Mike Dunlavey's Railroad networks example, is very useful.

share|improve this question

closed as not constructive by Ryathal, Walter, Robert Harvey, gnat, GlenH7 Dec 13 '12 at 19:41

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

9  
Regular expressions are finite state machines. –  chrisaycock Feb 14 '11 at 21:54
    
    
@chrisaycock They can be used to build more complex FSMs too. –  Evan Plaice Dec 13 '12 at 3:09
    
BTW, awesome question. –  Evan Plaice Dec 13 '12 at 3:37
1  
I don't understand why this question is marked as 'not constructive' Considering it's been almost 2 years since I first presented an answer that it is closed I'd argue that it actually was very constructive and on-topic. –  aqua Dec 14 '12 at 20:56

10 Answers 10

up vote 19 down vote accepted

A Safe (event triggered)

  • States: Multiple "locked" states, one "unlocked" state
  • Transitions: Correct combinations/keys move you from initial locked states to locked states closer to unlocked, until you finally get to unlocked. Incorrect combinations/keys land you back in the initial locked state (sometimes known as idle.

Traffic Light (time triggered | sensor [event] triggered)

  • States: RED, YELLOW, GREEN (simplest example)
  • Transitions: After a timer change RED to GREEN, GREEN to YELLOW, and YELLOW to RED. Could also be triggered on sensing cars in various (more complicated) states.

Vending Machine (event triggered, a variation of the safe)

  • States: IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS, etc, VEND, CHANGE
  • Transitions: State changes upon insertion of coins, bills, transition to VEND upon correct amount of purchase (or more), then transition to CHANGE or IDLE (depending how ethical your Vending Machine is)
share|improve this answer
    
+1 and more if I could. Everything looks good except the last one. It should be, IDLE, VEND, and CHANGE. The values are conditional and should be represented as the transition between IDLE and itself. You'd also want a state representing that an item has been selected. –  Evan Plaice Dec 13 '12 at 3:09
    
@EvanPlaice: Wouldn't selecting an item simply be the event that triggers a change from IDLE to VEND? Unless you're envisioning a method of confirming the selection before vending. –  Chris Dec 13 '12 at 16:18
    
Any chance of a diagram for these two? –  Slomojo Dec 15 '12 at 4:41

Border Gateway Protocol Example

BGP is a protocol which backs the the core routing decisions on the internet. It maintains a table to determine the reachability of hosts from a given node, and made the internet truly decentralized.

In the network, each BGP node is a peer, and uses a finite state machine, with one of six states Idle, Connect, Active, OpenSent, OpenConfirm, and Established. Each peer connection in the network maintains one of these states.

The BGP protocol determines the messages that are sent to peers in order to change their state.

BPG statechart.

BGP statechart

Idle

The first state Idle. In this state, BGP initializes resources, and refuses inbound connection attempts, and initiates a connection to the peer.

Connect

The second state Connect. In this state, the router waits for the connection to complete and transitions to the OpenSent state if successful. If unsuccessful, it resets the ConnectRetry timer and transitions to the Active state upon expiration.

Active

In the Active state, the router resets the ConnectRetry timer to zero and returns to the Connect state.

OpenSent

In the OpenSent state, the router sends an Open message and waits for one in return. Keepalive messages are exchanged and, upon successful receipt, the router is placed into the Established state.

Established

In the Established state, the router can send/receive: Keepalive; Update; and Notification messages to/from its peer.

More info about BGP is on wikipedia

share|improve this answer
    
+1 for the diagram –  tcrosley Feb 15 '11 at 0:21
    
@tcrosley - it's from wikipedia, so doesn't really deserve credit. –  Slomojo Feb 15 '11 at 0:22
1  
ok, +1 for including a diagram. :) –  tcrosley Feb 15 '11 at 0:33
    
I tried to fix the label of the chart to BGP, but it wouldn't let me - not enough characters :) –  Mike Dunlavey Feb 15 '11 at 1:14
1  
@Job - bit of a late response, sorry, but I now keep thinking this is far too esoteric an example, the Safe, Vending Machine, etc. are way more useful I think. –  Slomojo Apr 5 '12 at 5:53

They're useful for modelling all kinds of things. For example, an election cycle can be modelled with states along the lines of (normal government) --election called--> (early campaigning) --Parliament dissolved--> (heavy campaigning) --election--> (vote counting). Then either (vote counting) --no majority--> (coalition negotiations) --agreement reached--> (normal government) or (vote counting) --majority--> (normal government). I've implemented a variant on this scheme in a game with a political subgame.

They're used in other aspects of games too: AI is often state-based; transitions between menus and levels, and transitions upon death or level completed are often well modelled by FSMs.

share|improve this answer
    
++ Nice example. –  Mike Dunlavey Feb 15 '11 at 1:16
    
+1 Good example of a DFM (Deterministic Finite State Machine) because the paths. –  Evan Plaice Dec 13 '12 at 2:53

Simple FSM in Java

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

There you go. OK, it's not brilliant, but it shows the idea.

You'll often find FSMs in telecoms products because they offer a simple solution to an otherwise complex situation.

share|improve this answer
3  
They are also an important part of compiler construction in lexical analysis. –  jmq Feb 14 '11 at 21:21
    
@jmquigley, can you add an answer please? –  Slomojo Feb 14 '11 at 21:37
1  
I added a separate answer with a couple of links for you. –  jmq Feb 14 '11 at 22:00
    
@jmquigley - thanks :) –  Slomojo Feb 14 '11 at 22:09

OK, here's an example. Suppose you want to parse an integer. It would go something like dd* where d is an integer digit.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Of course, as @Gary said, you could disguise those gotos by means of a switch statement and state variable. Notice that can be structured to this code, which is isomorphic to the original regular expression:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Of course you can also do it with a lookup table.

Finite state machines can be made many ways, and many things can be described as instances of finite state machines. It's not a "thing" so much as a concept, for thinking about things.

Railroad Network Example

One example of a FSM is a railroad network.

There are a finite number of switches where a train can go onto one of two tracks.

There are a finite number of tracks connecting these switches.

At any time, a train is on one track, it can be sent to another track by crossing a switch, based on a single bit of input information.

share|improve this answer
    
(I've made an edit to your answer, I hope you approve.) –  Slomojo Feb 14 '11 at 21:36
    
@Slomojo: That's fine. Looks good. –  Mike Dunlavey Feb 15 '11 at 1:09

Finite State Machine in Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

That's the behavior of a single compute node in a distributed system, setting up a link based communication scheme. More or less. In Graphic form it looks something like this:

enter image description here

share|improve this answer
    
+1 Interesting. What does DGMM refer to? –  Evan Plaice Dec 13 '12 at 2:50
    
@EvanPlaice it's Distributed Maximal-Matching-based Minimum-Weighted Vertex Cover Algorithm (DGMM) ... a slightly abbreviated acronym, don't ask me where the G comes from. –  Slomojo Dec 13 '12 at 9:18
    
@slomojo The "G" is for "Generalized", the sequential algorithm from which this is derived uses a technique called generalized maximal matching. –  philosodad Jan 5 '13 at 1:17
    
@philosodad I assumed as much, but I dislike posting assumptions. –  Slomojo Jan 5 '13 at 3:31

I have found that thinking about/modelling a lift (elevator) is a good example of a finite state machine. It requires little in the way of introduction, but provides a far from trivial situation to implement.

The states are, for example, at the ground floor, at the first floor etc, and moving ground to first floor, or moving third to ground floor but currently between floor 3 and 2, and so on.

The effect of buttons in the lift cage and at the floors themselves provide inputs, the effect of which depend on both the button that is pressed along with the current state.

Each floor, except the top and bottom, will have two buttons: one to request the lift to go up, the other to go down.

share|improve this answer

The CSV parser used in the jquery-csv plug-in

It's a basic Chomsky Type III grammar parser.

A regex tokenizer is used to evaluate the data on a char-by-char basis. When a control char is encountered, the code is passed to a switch statement for further evaluation based on the starting state. Non-control characters are grouped and copied en masse to reduce the number of string copy operations needed.

The tokenizer:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

The first set of matches are the control characters: value delimiter (") value separator (,) and entry separator (all variations of newline). The last match handles the non-control char grouping.

There are 10 rules that the parser must satisfy:

  • Rule #1 - One entry per line, each line ends with a newline
  • Rule #2 - Trailing newline at the end of the file omitted
  • Rule #3 - First row contains header data
  • Rule #4 - Spaces are considered data and entries should not contain a trailing comma
  • Rule #5 - Lines may or may not be delimited by double-quotes
  • Rule #6 - Fields containing line breaks, double-quotes, and commas should be enclosed in double-quotes
  • Rule #7 - If double-quotes are used to enclose fields, then a double-quote appearing inside a field must be escaped by preceding it with another double quote
  • Amendment #1 - An unquoted field may or may
  • Amendment #2 - A quoted field may or may not
  • Amendment #3 - The last field in an entry may or may not contain a null value

Note: The top 7 rules are derived directly from IETF RFC 4180. The last 3 were added to cover edge cases introduced by modern spreadsheet apps (ex Excel, Google Spreadsheet) that don't delimit (ie quote) all values by default. I tried contributing back the changes to the RFC but have yet to hear a response to my inquiry.

Enough with the wind-up, here's the diagram:

CSV parser finite state machine

States:

  1. initial state for an entry and/or a value
  2. an opening quote has been encountered
  3. a second quote has been encountered
  4. an un-quoted value has been encountered

Transitions:

  • a. checks for both quoted values (1), unquoted values (3), null values (0), null entries (0), and new entries (0)
  • b. checks for a second quote char (2)
  • c. checks for an escaped quote (1), end of value (0), and end of entry (0)
  • d. checks end of value (0), and end of entry (0)

Note: It's actually missing a state. There should be a line from 'c' -> 'b' marked with state '1' because an escaped second delimiter means the first delimiter is still open. In fact, it would probably be better to represent it as another transition. Creating these is an art, there's no single correct way.

Note: It's also missing an exit state but on valid data the parser always ends on transition 'a' and none of the states are possible because there is nothing left to parse.

The Difference between States and Transitions:

A state is finite, meaning it can only be inferred to mean one thing.

A transition represents the flow between states so it can mean many things.

Basically, the state->transition relationship is 1->* (ie one-to-many). The state defines 'what it is' and the transition defines 'how it's handled'.

Note: Don't worry if the application of states/transitions doesn't feel intuitive, it's not intuitive. It took some extensive corresponding with somebody much smarter than I before I finally got the concept to stick.

The Pseudo-Code:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

Note: This is the gist, in practice there's a lot more to consider. For example, error checking, null values, a trailing blank line (ie which is valid), etc.

In this case, the state is the condition of things when the regex match block finishes an iteration. The transition is represented as the case statements.

As humans, we have a tendency to simplify low level operations into higher level abstracts but working with a FSM is working with low level operations. While states and transitions are very easy to work with individually, it is inherently difficult to visualize the whole all at once. I found it easiest to follow the individual paths of execution over and over until I could intuit how the transitions play out. It's king of like learning basic math, you won't be capable of evaluating the code from a higher level until the low level details start to become automatic.

Aside: If you look at the actual implementation, there are a lot of details missing. First, all impossible paths will throw specific exceptions. It should be impossible to hit them but if anything breaks they will absolutely trigger exceptions in test runner. Second, the parser rules for what is allowed in a 'legal' CSV data string are pretty loose so the code needed to handle a lot of specific edge cases. Regardless of that fact, this was the process used to mock the FSM prior to all of the bug fixes, extensions, and fine tuning.

As with most designs, it's not an exact representation of the implementation but it outlines the important parts. In practice, there are actually 3 different parser functions derived from this design: a csv-specific line splitter, a single-line parser, and a complete multi-line parser. They all operate in a similar manner, they differ in the way they handle newline chars.

share|improve this answer
    
whoa! very nice contribution. –  Slomojo Dec 13 '12 at 4:55
    
@Slomojo Thanks, I'm happy to share. I didn't go to school for CS so I had to learn this stuff on my own. It's really difficult to find real-world applications covering high-level CS topics like these online. I'm planning to eventually document the parser algorithm in fine detail so it can be useful to others like me in the future. This is a good start. –  Evan Plaice Dec 13 '12 at 5:03
    
I'm also self taught, but I started 30 years ago, so by now I've covered the CS curriculum :) I posted this question for people like you and me. I think it was significantly easier to learn very low level theory back then, simply because there was less distraction, and more opportunities to work close to the metal, although there wasn't really any internet, and we all lived in caves. –  Slomojo Dec 13 '12 at 9:05

Check out this link for some simple examples of lexical analysis (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

You can also check out the "dragon book" for examples (it's not light reading)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

share|improve this answer

In practice, State Machines are often used for:

  • Design purposes (modeling the different actions in a program)
  • Natural language (grammar) parsers
  • String parsing

One example would be a State Machine that scans a string to see if it has the right syntax. Dutch ZIP codes for instance are formatted as "1234 AB". The first part may only contain numbers, the second only letters. A State Machine could be written that keeps track of whether it’s in the NUMBER state or in the LETTER state and if it encounters wrong input, reject it.

This acceptor state machine has two states: numeric and alpha. The state machine starts in the numeric state, and starts reading the characters of the string to check. If invalid characters are encountered during any of the states, the function returns with a False value, rejecting the input as invalid.

Python code:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Source: (Finite-) State Machines in practice

share|improve this answer

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

2  
We normally expect people to put the contents of their sources in their answer, otherwise when said sources are not online anymore, your sources are gone forever and your answer useless. In other words a bunch of links does not answer the author's question. –  Ramhound Oct 4 '12 at 12:32

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