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.

  • 12
    Regular expressions are finite state machines. Commented Feb 14, 2011 at 21:54
  • 6
    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
    Commented Dec 14, 2012 at 20:56
  • 2
    @aqua - it's really more of a problem with stack.Programmers, it's mandate is to answer questions, very very specific questions, that have one answer. However, questions such as this which are valuable, are not deemed as "constructive" (a very poor definition of the term, in IMNSHO.) based on the definition of Stack sites in general. Frankly for Programmers to be truly useful, it should adopt a less zealous adherence to this particular rule, but I'm old, tired and otherwise engaged, to put the requisite effort into "trying to fix stupid."
    – ocodo
    Commented Dec 15, 2012 at 2:39
  • 1
    Effectively the real problem is that Stack sites are, frankly, one of the very few high quality resources, that are well known, and collaborative, and have a good, readable format. It appears that this reductionism on Stack, really points to a need for site format that is for educational "questions" (probably without using the E word.)
    – ocodo
    Commented Dec 15, 2012 at 4:34
  • 3
    I would still implore people to reopen this question, because more examples, would be great. The sad fact is, if new answers hadn't been added, the question would've remained open.
    – ocodo
    Commented Dec 15, 2012 at 4:40

10 Answers 10


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)
  • +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. Commented Dec 13, 2012 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.
    – Misko
    Commented Dec 13, 2012 at 16:18
  • Any chance of a diagram for these two?
    – ocodo
    Commented Dec 15, 2012 at 4:41
  • These are the same as the examples given in the FSM Wikipedia page, which also includes elevators: "Simple examples are vending machines, which dispense products when the proper combination of coins is deposited, elevators, whose sequence of stops is determined by the floors requested by riders, traffic lights, which change sequence when cars are waiting, and combination locks, which require the input of combination numbers in the proper order."
    – icc97
    Commented Aug 16, 2018 at 9:43
  • 1
    @icc97 FSM examples are plentiful and common throughout everyday life. Incidentally, the stack exchange post pre-dates the inclusion of the example information on the Wikipedia page :)
    – aqua
    Commented Aug 29, 2018 at 21:42

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


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


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.


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


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.


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

  • @tcrosley - it's from wikipedia, so doesn't really deserve credit.
    – ocodo
    Commented Feb 15, 2011 at 0:22
  • 1
    ok, +1 for including a diagram. :)
    – tcrosley
    Commented Feb 15, 2011 at 0:33
  • I tried to fix the label of the chart to BGP, but it wouldn't let me - not enough characters :) Commented Feb 15, 2011 at 1:14
  • There has to be a better way to draw this.
    – Job
    Commented Feb 15, 2011 at 3:09
  • 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.
    – ocodo
    Commented Apr 5, 2012 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.

  • ++ Nice example. Commented Feb 15, 2011 at 1:16
  • 1
    +1 Good example of a DFM (Deterministic Finite State Machine) because the paths. Commented Dec 13, 2012 at 2:53

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


  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


  • 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() {
  value = ""

endOfEntry() {
  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
        state = 0
      if(un-delimited data)
        value += match
        state = 3
    case 1:
      if(second delimiter encountered)
        state = 2
      if(non-control char data)
        value += match
        state = 1
    case 2:
      if(escaped delimiter)
        state = 1
        state = 0
        state = 0
    case 3:
        state = 0
        state = 0

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.

  • 1
    whoa! very nice contribution.
    – ocodo
    Commented Dec 13, 2012 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. Commented Dec 13, 2012 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.
    – ocodo
    Commented Dec 13, 2012 at 9:05

Simple FSM in Java

int i=0;

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


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.

  • 3
    They are also an important part of compiler construction in lexical analysis.
    – jmq
    Commented Feb 14, 2011 at 21:21
  • @jmquigley, can you add an answer please?
    – ocodo
    Commented Feb 14, 2011 at 21:37
  • 1
    I added a separate answer with a couple of links for you.
    – jmq
    Commented Feb 14, 2011 at 22:00

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.


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

    if (!isdigit(*p)) goto error;
    goto state1;
    if (!isdigit(*p)) goto success;
    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)){
    // 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.

  • (I've made an edit to your answer, I hope you approve.)
    – ocodo
    Commented Feb 14, 2011 at 21:36
  • @Slomojo: That's fine. Looks good. Commented Feb 15, 2011 at 1:09

Finite State Machine in Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      @next = :exchange
    when :exchange
      @next = :choose
    when :choose
    when :done
      @next = :done

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

  • +1 Interesting. What does DGMM refer to? Commented Dec 13, 2012 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.
    – ocodo
    Commented Dec 13, 2012 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
    Commented Jan 5, 2013 at 1:17
  • @philosodad I assumed as much, but I dislike posting assumptions.
    – ocodo
    Commented Jan 5, 2013 at 3:31

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


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



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



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


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