Teach me: Finite State Machines (FSM) - Hardcore Theory

Not for 'how-to' coding questions but PHP theory instead, this forum is here for those of us who wish to learn about design aspects of programming with PHP.

Moderator: General Moderators

User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

This is probably quite an advanced theory-based topic, but this is the place to do it.

I completely understand the concept of a FSM, but I'd like to see one get written, from the ground-up, in PHP (if possible). It's one of those things I probably missed out on by not taking CS at uni.

So, say I have a Car class that has methods:

Code: Select all

Car {
  const GEAR_ONE = 1;
  const GEAR_TWO = 2;
  const GEAR_THREE = 3;
  const GEAR_REVERSE = -1;
  
  start()
  changeGear($gearNumber)
  drive()
  brake()
  turnLeft()
  turnRight()
  stop()
}
Massively simplified for obvious reasons.

This is hopefully a simple example? I'm not being very accurate with the logic/physics here for the sake of simplicity...

A Car can only be started if:

It is "not started".

Once it is started, it is "started".

A Car can only drive if:

It is "started" AND it is "not braking".

Once it is driving, it is "driving".

A Car can only turn left or right if:

It is "driving"

A Car can only change gear if it:

It is "started".

This has no state change effect.

A Car can only change gear into reverse if:

It is "not driving" and it is "started".

This has no state change effect.

A car can only brake if:

If it is "started"

When braking, (simplicity) the car is "not driving".

A Car can only stop if:

It is "started" AND it is "not driving"

Once stopped, it is "not started".

So this is a pretty simple model for the states this FSM needs.

Does anybody want to help me create a state machine to model this? I could hack my way through it (and I'm expecting people to post such hacked solutions... please don't post a solution if you don't know what I mean by FSM), but what I'm looking for is the generally accepted algorithm for tackling a FSM.

I see a lot of talk of lookup tables for state transitions. Although this example is so simple that it's not needed, it would be helpful (for my learning benefit) if we could throw that in.

Does anyone have experience in this area?

I'm going to be away for a few hours but I'm looking forward to coming back and watching this discussion evolve.

Again, please don't post solutions that "just work" if what you're posting is not a traditional finite state machine. The point of the exercise is to learn :)
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Christopher »

Must ... not ... get ... involved ... in ... state ... machine ... discussion ... must ... resist ... cannot ... hold ... out ... much ... longer ...

Urgh.

State-machines really aren't that obtuse. The problem is that good state machine code is usually done with code generation and is not very human readable.

You have some of the basics. You really need three main things -- Events, States and Transitions. It is usually easier to first list all of those and then create a table that itemizes every Event that can happen in every State and the Transition that occurs when that happens. Then we would just need to decide how to express that in code -- hopefully some fairly clear but not very efficient OOP design.

So for example, your Events might be:
- Turn ignition key clockwise
- Turn ignition key anti-clockwise
- Press gas pedal
- Press brake pedal
- Turn steering wheel left
- Turn steering wheel right

States might be:
- Engine off
- Engine on not moving
- Accelerating
- Steady speed
- Decelerating
- Accelerating turning right
- Steady speed turning right
- Decelerating turning right
- Accelerating turning left
- Steady speed turning left
- Decelerating turning left
(#10850)
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

Awesome. I'll chime back into this later... I really have to dash (I'm responsible for the work social club events, and tonight is one of those events).

Looking forward to some good old discussion here :)
webaddict
Forum Commoner
Posts: 60
Joined: Wed Mar 14, 2007 6:55 am
Location: The Netherlands

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by webaddict »

Well, I haven't the time to actually implement the FSM, but I would like to give you a heads-up. The number one thing I do when I encounter a FSM (and you do so more often than you'd think), is writing a directed graph for it, essensially documenting it before you start coding it. The problem with FSM's is that when the code is written, everything becomes a bit unclear, and problems will arise. Having a simple graph for it, it's easier to see what went wrong and where.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

Ok, back from my night out, though it is nearly 1am here ;)

If we were to create a table for those events/states, it would look something like this. I had to adjust the events since I wasn't sure what should happen if say, you're accelerating and turning then you apply the brake.

Code: Select all

                            Turn Ignition On | Turn Ignition Off | Press Gas     | Press Brake   | Steer Left                | Steer Right
--------------------------------------------------------------------------------------------------------------------------------------------------------
Engine Off                 | Engine on        | X                 | X             |               |                           |
Engine On                  | X                | Engine off        | Accelerating  |               |                           |                         
Accelerating               | X                | X                 |               | Steady Speed  | Accelerating Turning Left | Accelerating Turning Right
Steady Speed               | X                | X                 | Accerating    | Decelerating  | Turning Left              | Turning Right
Decelerating               | X                | X                 | Steady Speed  |               | Decelerating Turning Left | Decelerating Turning Right
Decelerating Turning Right | X                | X                 | Turning Right |               | Decelerating Turning Left |
Decelerating Turning Left  | X                | X                 | Turning Left  |               |                           | Decelerating Turning Right
Accelerating Turning Right | X                | X                 |               | Turning Right | Accelerating Turning Left | 
Accelerating Turning Left  | X                | X                 |               | Turning Left  |                           | Accelerating Turning Right
An X means the event is not permitted. A blank cell means the event does nothing. Anything else specifies the new state.

Do we turn this into an associative array? And if we did, woud that be the "lookup table" I've seen mentioned a few times? :)

PS: According to the above model, this car can be started, and immediately stopped. But once you start driving it you're doomed :P
josh
DevNet Master
Posts: 4872
Joined: Wed Feb 11, 2004 3:23 pm
Location: Palm beach, Florida

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by josh »

Hmm isn't this kind of like application controllers? Don't these break down as conditional logic piles up? For example representing the english grammar as a word chain would be impossible. I understand they're applicable to certain systems, like elevator control, etc.. high reliability simple systems, but I'm confused as to what is interesting about the stuff?
Chris Corbyn wrote: According to the above model, this car can be started, and immediately stopped. But once you start driving it you're doomed :P
That's because you're modeling domain knowledge as a flow chart, which only allows binary decisions. Bayesian statistics or nueral networks extend FSMs with "fuzzy" logic.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

jshpro2 wrote:Hmm isn't this kind of like application controllers? Don't these break down as conditional logic piles up?
Are you suggesting that FSMs are not to be used? Unless I'm misreading your words? :)

As I understand it, FSMs are used to tackle some very complex logic in a clean way.

To pinpoint the reason I'm looking to gain a better understanding of (the guts of) a FSM, I'm playing around with parsing and the use of a FSM is the most efficient way to write one. I'm trying to understand the algorithm used in bison/yacc. But that's a side-point, FSMs have all kinds of applications and as far as I understand it, they *should* be fairly commonly understood in computer science (doesn't *every* computer program boil down to a FSM in the end?). I feel a little uneducated in this respect :P I actually have never written even a simple FSM so I'm hoping to learn something here.
mintedjo
Forum Contributor
Posts: 153
Joined: Wed Nov 19, 2008 6:23 am

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by mintedjo »

This is one of those things that people at Uni hate doing - so by not going to Uni you probably avoided something which you would have hated. And if you are anything like me you didn't miss out on anything because one year on I've forgotten everything we learned about finite state machines. The only thing I do remember is drawing lots of flow diagrams...
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Christopher »

Chris Corbyn wrote:If we were to create a table for those events/states, it would look something like this. I had to adjust the events since I wasn't sure what should happen if say, you're accelerating and turning then you apply the brake.
Well in this model we probably only have one speed, so you can only go from stopped to steady speed and back to stopped.
Chris Corbyn wrote:

Code: Select all

                            Turn Ignition On | Turn Ignition Off | Press Gas     | Press Brake   | Steer Left                | Steer Right
--------------------------------------------------------------------------------------------------------------------------------------------------------
Engine Off                 | Engine on        | X                 | X             |               |                           |
Engine On                  | X                | Engine off        | Accelerating  |               |                           |                         
Accelerating               | X                | X                 |               | Steady Speed  | Accelerating Turning Left | Accelerating Turning Right
Steady Speed               | X                | X                 | Accerating    | Decelerating  | Turning Left              | Turning Right
Decelerating               | X                | X                 | Steady Speed  |               | Decelerating Turning Left | Decelerating Turning Right
Decelerating Turning Right | X                | X                 | Turning Right |               | Decelerating Turning Left |
Decelerating Turning Left  | X                | X                 | Turning Left  |               |                           | Decelerating Turning Right
Accelerating Turning Right | X                | X                 |               | Turning Right | Accelerating Turning Left | 
Accelerating Turning Left  | X                | X                 |               | Turning Left  |                           | Accelerating Turning Right
An X means the event is not permitted. A blank cell means the event does nothing. Anything else specifies the new state.
This table is handy to think about the combinations, althuogh you have not really filled it out right. An examples, when the car is Off, Press Gas does not do anything just like Press Brake. And Press Brake when Decelerating would go to Engine On Stopped
Chris Corbyn wrote:PS: According to the above model, this car can be started, and immediately stopped. But once you start driving it you're doomed :P
No, you just missed some of the transitions.
Chris Corbyn wrote:Do we turn this into an associative array? And if we did, woud that be the "lookup table" I've seen mentioned a few times? :)
As mentioned above, you want to get this table right or do a directed graph diagram to get everything. Then you probably need to express it in what you might call a Transition Table:

Code: Select all

Starting State             | Event                     | Ending State
--------------------------------------------------------------------------------------------------------------------------------------------------------
Engine Off                 | Turn Ignition On          | Engine On
Engine On                  | Turn Ignition Off         | Engine off                          
Engine On                  | Press Gas                 | Accelerating
(#10850)
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Christopher »

jshpro2 wrote:Hmm isn't this kind of like application controllers?
Yes, for example it is one way that Skeleton does forms as a three state state-machine (init, submit, done) using an Application Controller.
jshpro2 wrote:Don't these break down as conditional logic piles up? For example representing the english grammar as a word chain would be impossible. I understand they're applicable to certain systems, like elevator control, etc.. high reliability simple systems, but I'm confused as to what is interesting about the stuff?
So you really want us to discuss why you don't find state-machines interesting? ;)
jshpro2 wrote:That's because you're modeling domain knowledge as a flow chart, which only allows binary decisions. Bayesian statistics or nueral networks extend FSMs with "fuzzy" logic.
That's the point of a state-machine, and obviously there are other tools to achieve results that may be more applicable in different situations. A thing about math and logic is that there are lots of different kinds of problems and mathematicians have figured out lots of different ways to solve things -- searching for simpler ways to solve something given certain conditions. So obviously yes, Bayesian stats and neural networks are other ways to solve similar problems.
(#10850)
User avatar
sergio-pro
Forum Commoner
Posts: 88
Joined: Sat Dec 27, 2008 12:26 pm

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by sergio-pro »

Hi all.

Here is a kind of draft.
Its on java, but you seem to be familiar with it Chris.

Code: Select all

 
 
class FSM {
  
  protected State currentState;
 
  public FSM(State initialState) {
    currentState = initialState;
  }
 
  public void handleEvent(String e) {
    currentState = currentState.handleEvent(e);
  }
 
}
 
class CarFSM extends FSM {
 
  private EnginOffStoppedState engineOff = new EnginOffStoppedState(this);
  private EngineOnStoppedState engineOn = new EngineOnStoppedState(this);
  private EngineOffMovingState engineOffMoving = new EngineOffMovingState(this);
  private EngineOnMovingState engineOnMoving = EngineOnMovingState(this);
 
  public static final String EVT_START_ENGINE = "startEngine";
  public static final String EVT_STOP_ENGINE = "stopEngine";
  public static final String EVT_ACCELERATE = "accelerate";
  public static final String EVT_BREAK = "break";
 
  public CarFSM() {
    super(engineOff);
  }
 
 
  public void startEngine() {
    handleEvent(EVT_START_ENGINE);
  }
 
  ... - other events
 
 
 
}
 
class EngineOnMovingState extends State {
 
  private CarFSM carFsm;
 
  public EngineOnMovingState(CarFSM carFsm) {
    this.carFsm = carFsm;
  }
 
  public function handleEvent(String e) {
    if (e.equals(CarFSM.EVT_STOP_ENGINE)) {
      return carFsm.engineOffMoving;  
    } else if (e.equals(CarFSM.EVT_BREAK)) {
      return carFsm.engineOn;  
    }
  }
 
} 
 
 
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Christopher »

Now simply code event handler classes for the other 999 states in you system...
(#10850)
User avatar
sergio-pro
Forum Commoner
Posts: 88
Joined: Sat Dec 27, 2008 12:26 pm

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by sergio-pro »

We all usually do so.

Any program is FSM in some way :)
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Chris Corbyn »

@arborint, thanks for correcting me :) I had a feeling I was doing something wrong there since I was running out of horizontal space!

I'll go ahead a re-do that table, taking into account those missing transitions too.

@sergio-pro, thanks for showing that code. I'm familiar with the state pattern implementation though I hadn't ever really thought of implementing the state pattern as being implementing a FSM. Seems obvious now. Like arborint says, you'd have to hard-code a lot of classes for that to work properly and you'd soon get tangled in the logic...
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Re: Teach me: Finite State Machines (FSM) - Hardcore Theory

Post by Christopher »

Yes, if you implement using a State-Transition table then instead of one handler per State, you only need one handler per Event. There are always many, many more States than Events.
(#10850)
Post Reply