Page 1 of 1

Finite State Machines Understand what they are by example Rate Topic: ***** 2 Votes

#1 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Posted 05 March 2010 - 11:25 AM

Finite State Machines

Introduction

There are certain types of programming problem that do not readily lend themselves to conventional programming models (if such a thing exists). Consider the example of the telephone (mobile if you are but young, the old bakalite GPO public telephones if you are my age). A telephone can be in quite a number of states. It can be 'on hook' meaning that it is both ready to receive incoming calls and is also ready to dial out, should you choose to do so. Let's hear the telephone ring. Listen, ring ring ... ring ring. The telephone is in a ringing state. Let's not bother to answer it (we can see it's our bank manager). The ringing stops. So we have two states so far, on-hook and ringing. We also can say that we have two transisions between those two states. There is the transition between on-hook -> ringing and a transition between ringing -> on-hook. Damn, the phone has started ringing again. Ring ring ... ring ring ... ring ring. I supose we had better answer it this time, it's our best mate. We press the answer button, or lift the receiver off the hook. The ringing stops, so we must have gone through a new transition to a new state. "Hello", we hear "hello Martyn are you there?", we are currently away with the fairies pondering this new transition and this new state. "Click", the call ends and we appear to be back in the on-hook state. That was interesting we think to ourselves. What do we call that new state I wonder. Well, connected will do nicely. So we have ringing -> connected. Ah, but we also have connected -> on-hook as well. So let's list these

1. on-hook -> ringing
2. ringing -> on-hook
3. ringing -> connected
4. connected -> on-hook

Now, can we go from on-hook to busy? The answer is no we cannot. Can we go from busy -> ringing? That would be an interesting thought. You are in the middle of a telephone conversation and the phone starts ringing!

Now let's look at the making a call side of things. We better had as our mate will be concerned that we answered the call, but did not speak. We press the call button or lift the receiver and hear the dial tone. There is a transition for you and a new state. We have gone from on-hook to off-hook. We dial the number for our mate. We hear the remote end ringing tones. There is another state for you. Let's call that remote-ringing. So we have on-hook -> off-hook, and we have off-hook -> remote ringing. Ooops, I hear you say ... we missed a state and a transition somewhere, because when we go off hook, we do not immediately get remote ringing. We went through a dialing state. So we actually performed the following

5. on-hook -> off-hook
6. off-hook -> dialing
7. dialing -> remote-ringing

Our mate answers the telephone and we have entered yet another state connected. We have a good old conversation with our mate, finish the conversation and place the phone back on-hook, or press the end-call button. That gives us

8. remote-ringing -> connected
9. connected -> disconnected
10. disconnected -> on-hook

Now we have not discussed items 11 and 12 above. If your mate accidentally presses the end-call button on his mobile, you are in a disconnect state. In this state, you cannot receieve calls, nor can you dial out. You have to terminate your side by pressing your call-end on the mobile or replace the reciever back onto the hook.

There are a few more things we need to discuss here, that have not been mentioned thus far. If you press the call button and hear the outgoing line tone, you may decide that you will wait a few more minutes before calling your mate ... so you press the end-call button. Thats off-hook -> on-hook. You may start dialing the number then decide to press the end-call button. Thats dialing -> on-hook. You may well get the remote ringing tone, but before it's picked up at the other end, decide to leave it. That will give you remote-ringing -> on-hook. Finally, you may well find you get the remote caller busy tone, and hang up. That gives us dialing -> remote-busy and finally remote-busy -> on-hook. These are given below:

11. off-hook -> on-hook
12. dialing -> on-hook
13. dialing -> remote-busy
14. remote-ringing -> on-hook
15. remote-busy -> on-hook

ok, so now we have all the states and all the transitions we can go through for a telephone (I am not bothering with states such as error, battery low etc).

The Finite State Machine

A finite state machine is any model that has a fixed number of states with a clear starting and ending state. If you look at the diagram below, you will see that we have drawn is a state-event diagram for our simple finite state machine.

Posted Image
Figure 1.

This FSM consists of 8 states, and 15 transitions that can exist between those states. The starting and ending states in this example are one of the same, namely S1. In order to progress from one state to another state, some event has to occur which causes a transition between states. At any given instant in time the finite state machine must always have a current state.

More complex finite state machines may consist of hundreds, if not thousands of states and transitions. Entering a given state, may well invoke some 'sub' state machine, that is in itself a complete finite state machine.

Programming the Finite State Machine

Before I move on to showing you how to preogram a finite state machine, it is important that you have read my tutorial entitled "... introducing the amazing this pointer" found here. The following code relies heavily on the mechanism outlined in that tutorial, so if you haven't read it please do so.

The code below implements the finite state machine for our telephone example above, using the state-transition diagram provided in Figure 1.

Each of the eight states (numbered state_1 through to state_8) are derived from a base class called state. Each of the derived states implements it's own version of the virtual change_state function declared in the base class. Each of the derived states is responsible for dealing with it's own events, and which states to progress to based on those events.

The finite_state_machine class declared just before the end of the code is simply a driver for the system, simulating events in terms of a random number which the current_state object uses to determine which transition to follow to a new state. If you have any problems understanding this code, please do not hesitate to ask.

#include <iostream>
#include <ctime>
 
using namespace std; 

// Basic state from which all other states are derived
class state {
    private:
        int this_state;
    public:
        state(int new_state) : this_state(new_state) { };
        virtual state * change_state(int choice) = 0;
        void wait_a_second();
};

// On hook state, also the start and end state
class state_1 : public state {
    public:
        state_1() : state(1) { };
        state * change_state(int choice);
};

// Ringing state
class state_2 : public state {
    private:
        int ring_count;
    public:
        state_2() : state(2), ring_count(0) { };
        state * change_state(int choice);
};

// Connected state
class state_3 : public state {
   private:
        int count;
    public:
        state_3() : state(3), count(0) { };
        state * change_state(int choice);
};

// Off hook state
class state_4 : public state {
   private:
        int count;
    public:
        state_4() : state(4), count(0) { };
        state * change_state(int choice);
};

// Dialling state
class state_5 : public state {
    private:
        int ring_count;
    public:
        state_5() : state(5), ring_count(0) { };
        state * change_state(int choice);
};

// Remote ringing state
class state_6 : public state {
    private:
        int count;
    public:
        state_6() : state(6), count(0) { };
        state * change_state(int choice);
};

// Remote busy state
class state_7 : public state {
    public:
        state_7() : state(7) { };
        state * change_state(int choice);
};

// Disconnected state
class state_8 : public state {
    public:
        state_8() : state(8) { };
        state * change_state(int choice);
};

// A cross-platform wait a second or two method
void state::wait_a_second() {
    time_t time_current = time(NULL);
    while ( time(NULL) <= time_current+1 );
}

// On hook state. Transition to ringing or off-hook
state * state_1::change_state(int choice) {
    cout << "on hook" << endl;
    if ( choice == 0 )
        reinterpret_cast<state_2 *>(this)->state_2::state_2(); 
    else
        reinterpret_cast<state_4 *>(this)->state_4::state_4(); 
    wait_a_second();
    return this; 
};

// Ringing state. Transition to connected or on-hook
state * state_2::change_state(int choice) {
    if ( ring_count == 0 ) cout << "ringing" << endl;
    if ( choice == 1 ) {
        reinterpret_cast<state_3 *>(this)->state_3::state_3();
        wait_a_second();
        return this; 
    }
    ring_count++;
    if ( ring_count == 5 ) {
        reinterpret_cast<state_1 *>(this)->state_1::state_1();
    }
    wait_a_second();
    return this; 
};

// Connected state. Transition to on-hook or disconnected
state * state_3::change_state(int choice) {
    if ( count == 0 ) cout << "connected" << endl; 
    count++;
    if ( choice == 1 ) {
        if ( count == 5 ) {
            reinterpret_cast<state_1 *>(this)->state_1::state_1();
        }
        wait_a_second();
        return this; 
    }
    if ( count == 5 ) {
        reinterpret_cast<state_8 *>(this)->state_8::state_8();
    }
    wait_a_second();
    return this; 
};

// Off hook state. Transition to on-hook or dialling
state * state_4::change_state(int choice) {
    cout << "off hook" << endl; 
    if ( choice == 1 ) {
        reinterpret_cast<state_1 *>(this)->state_1::state_1();
        wait_a_second();
        return this; 
    }
    reinterpret_cast<state_5 *>(this)->state_5::state_5();
    wait_a_second();
    return this; 
};

// Dialing state. Transition to remote ringing, remote busy or on-hook
state * state_5::change_state(int choice) {
    cout << "dialling" << endl; 
    if ( choice == 0 ) {
        reinterpret_cast<state_6 *>(this)->state_6::state_6(); 
        wait_a_second();
        return this; 
    }
    if ( choice == 1 )
        reinterpret_cast<state_7 *>(this)->state_7::state_7();
    else
        reinterpret_cast<state_1 *>(this)->state_1::state_1();
    wait_a_second();
    return this; 
};

// Remote ringing state. Transition to connected or on-hook
state * state_6::change_state(int choice) {
    if ( count == 0 ) cout << "remote ringing" << endl; 
    if ( choice == 1 ) {
        reinterpret_cast<state_3 *>(this)->state_3::state_3();
        wait_a_second();
        return this; 
    }
    count++;
    if ( count == 5 ) {
        reinterpret_cast<state_1 *>(this)->state_1::state_1();
    }
    wait_a_second();
    return this; 
};

// Remote busy state. Transition to on-hook
state * state_7::change_state(int choice) {
    cout << "remote busy" << endl; 
    reinterpret_cast<state_1 *>(this)->state_1::state_1(); 
    wait_a_second();
    return this; 
};

// Disconnected state. Transition to on-hook
state * state_8::change_state(int choice) {
    cout << "disconnected" << endl; 
    reinterpret_cast<state_1 *>(this)->state_1::state_1(); 
    wait_a_second();
    return this; 
};

// The finite state machine
class finite_state_machine {
    private:
        state * current_state;
    public:
        finite_state_machine() : current_state(new state_1()) { srand(static_cast<unsigned int>(time(NULL))); };
        void next_state(int choice) { current_state = current_state->change_state(choice); };
        void simulate_telephone() {
            while ( true ) {
                int state_shift = rand()%3;
                next_state(state_shift);
            }
        };
};

// main routine
int main () {
    finite_state_machine fsm;
    fsm.simulate_telephone();
}



Try compiling and running the code and watch the telephone being used. It's oddly theraputic (or maybe that's because I am just :crazy:

Hopefully, you will now have a better understanding of finite state machines, and maybe will have a go at building one or two.

Is This A Good Question/Topic? 3
  • +

Replies To: Finite State Machines

#2 PlasticineGuy  Icon User is offline

  • mov dword[esp+eax],0
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,436
  • Joined: 03-January 10

Posted 05 March 2010 - 08:05 PM

Excellent tutorial Martyn. May I note that in these functions the argument is never used:
// Remote busy state. Transition to on-hook
state * state_7::change_state(int choice) {
    cout << "remote busy" << endl; 
    reinterpret_cast<state_1 *>(this)->state_1::state_1(); 
    wait_a_second();
    return this; 
};

// Disconnected state. Transition to on-hook
state * state_8::change_state(int choice) {
    cout << "disconnected" << endl; 
    reinterpret_cast<state_1 *>(this)->state_1::state_1(); 
    wait_a_second();
    return this; 
};


Was This Post Helpful? 0
  • +
  • -

#3 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Posted 05 March 2010 - 09:43 PM

The methods in question are overridden from the base class. Some of the derived classes require a parameter, so so they all have to have it.
Was This Post Helpful? 1
  • +
  • -

#4 surrender  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 29-September 10

Posted 29 September 2010 - 12:01 PM

Thanks Martyn for this great introduction with Finite state machines in C++!

I tried to build the code, but got a bunch of same errors:
In member function 'virtual state* state_1::change_state(int)'
error: cannot call constructor 'state_2::state_2' directly

What can I do to resolve this problem?
I work with the gnu g++ compiler.

Regards,

surrender

the Netherlands
Was This Post Helpful? 0
  • +
  • -

#5 PlasticineGuy  Icon User is offline

  • mov dword[esp+eax],0
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,436
  • Joined: 03-January 10

Posted 20 August 2011 - 06:28 AM

Sadly, as mentioned in a different topic the code does not compile on g++. Works for Visual C++ though.

Martyn, I re-read the tutorial, and I wrote this macro:
#define convert_to(target) reinterpret_cast<target*>(this)->target::target()
Is this naive, or a decent idea to clean up the code?

This post has been edited by PlasticineGuy: 20 August 2011 - 06:37 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1