The magic of Finite State Machines

[iago]

If any of you have tackled an input problem, you know that parsing a string can be tricky and annoying.  Recently, I've learned how to use finite state machines properly, and they are extremely useful.  If you read this, you will probably be much better off while processing input.

What you basically do is set up a series of states, and transitions from the states.  You have to visualize it, drawing it isn't necessary.  For each state, you should have a clear comment on exactly what it does, and what state, if any, it moves into.  I'll do a small diagram of how to process each line of a configuration file (name=value pairs, with \ escapes):

           _________________
          |                 |
          | ReadingKeySlash |
          |_________________|
             ^           |
             |         read anything
           read \      add to key
             |           |
             |           v
           ________________
          |                | -- [Not a \ or =] ---- [Add to key]-------
start --> |   ReadingKey   |                                           |
          |________________| <-----------------------------------------
                 |
              read =
                 |
                 |
                 v
        ________________
       |                | -- [Not a \] ---- [Add to value]-----
       |   ReadingValue |                                      |
       |________________| <-------------------------------------
          |           ^
          |           |
          |         read anything
        read \      add to value
          |           |
          v           |
        ___________________
       |                   |
       | ReadingValueSlash |
       |___________________|

I didn't draw in the end states, since I was out of room.  Here are the state descriptions I wrote up for them:

enum ReadStates
{
   /** This is the starting state.  If it sees a \, it moves into ReadingKeySlash.  If it sees a =, it
    * moves to ReadingValue and ignores it.  If the end of the string is reached in this state,
    * the string's value is considered empty, "".  */
   ReadingKey,
   
   /** It saw a \ while reading the key,  This indicates that the next character is read directly.  The
    * next value is always added to the string, then it always moves into ReadingKey.  If the end of the
    * string is reached in this state, it means that a newline should be appended, and it should continue
    * reading at the next line.  If there is no next line, it is invalid and this should be discarded. */
   ReadingKeySlash,
   
   /** This state is reached after a = is found.  If it sees a \, it moved into ReadingValueSlash.   
    * If it sees the end of the string, it accepts the input and the machine ends.  */
   ReadingValue,
   
   /** It saw a \ while reading the value.  This indicates that the next character is read directly.  The
    * next value is awlays added to the string, then it always moved back into ReadingValue.  If the end
    * of the string is reached in this state, itmeans that a newline should be appeneded, and it should
    * continue reading at the next line.  If there is no next line, it is invalid and this should be
    * discarded.  If there is no next line, then the input is accepted.  If an = is reached in this
    * state, it is ignored.
    */
   ReadingValueSlash
}

Obviously, this is a very basic machine.  Here's the states for a slightly more complicated one (I drew it on paper, but that paper is long gone).  It is for a microcontroller, and involves switches (SW0/SW1)  and LEDs, but it's basically the same idea (for full code, get it here):

typedef enum
{
    /* The catch-all state; if anything weird happens, it goes back to here, and
     * is dealt with as if we just began */
    START,

    /* SW0 was pressed the first time (possibly of a double-press) and possibly held
     * (in the case of clearing the LEDs.  This is basically a buffer state, waiting
     * for a single press, double-press, or both-button-press */
    SW0_DOWN_1,

    /* SW0 was released after having been pressed.  If it's pressed again, it's a
     * double-press.  Otherwise, go back to start */
    SW0_UP,

    /* SW0 was double-clicked, and is being held down.  If it's held down for
     * two more seconds, it's cleared; otherwise, goes back to start. */
    SW0_DOWN_2,

    /* SW1 was pressed, and is being held for less than 500ms.  This is a buffer
     * state, in case both buttons are pressed at the "same time" */
    SW1_DOWN,

    /* SW1 has been held for more than 500ms.  It will blink every second, and if
     * anything changes it goes back to start */
    SW1_HOLDING,

    /* After holding SW0 for more than 2 seconds, it enters this state.  It will
     * continue clearing the LEDs until it's released. */
    CLEAR_WAIT,

    /* Both buttons have been pressed at the same time, and are being held down. 
     * as soon as something changes, go back to start */
    BOTH_DOWN
} q3_states;

If you become comfortable with creating machines like this, then doing inputs like reading in a configuration file, reading in a user's inputs, and anything else like that will be much, much easier. 

[Chavo]

I don't know about you "software" people, but this is like 'how-to-use-a-microchip-101' type stuff.  No insult intended :)

EDIT: I just realized this is in the tutorials section, which makes a whole lot more sense than my original impression of iago discovering something new  :P

[iago]

I don't know about you "software" people, but this is like 'how-to-use-a-microchip-101' type stuff.  No insult intended :)

EDIT: I just realized this is in the tutorials section, which makes a whole lot more sense than my original impression of iago discovering something new  :P

Haha, yeah, it's the first thing he taught us in our microcontrollers class.  I'd known about FSM's before, but I hadn't learned to use them well until just recently. 

I'm posting this here for the benefit of others here, most of whom have probably never heard of a FSM before :P

[Sidoh]

I'm posting this here for the benefit of others here, most of whom have probably never heard of a FSM before :P

I've heard about it and have actually done a bit of reading on it, but I have not studied it enough to know how to use/implement them.  I read it in The New Turing Omnibus by A.K. Dewdny; it's an algorithmic book.  There's some neat stuff in there! :)

But yeah... I'll have to read this when my attention span is a bit less controlled by mountain dew, confusing and lack of sleep. :)

[iago]

I'm posting this here for the benefit of others here, most of whom have probably never heard of a FSM before :P

I've heard about it and have actually done a bit of reading on it, but I have not studied it enough to know how to use/implement them.  I read it in The New Turing Omnibus by A.K. Dewdny; it's an algorithmic book.  There's some neat stuff in there! :)

But yeah... I'll have to read this when my attention span is a bit less controlled by mountain dew, confusing and lack of sleep. :)

This is much MUCH simpler than a Turing Machine.  There are many levels of Finite State Machines, the most important ones being:
Turing > Pushdown Automata > Finite Automata

The ones I describe here are Finite Automata.  They are useful for most things.  If for some reason you need to design a full programming language, or interpret more complicated languages, then Pushdown Automata should be used.

[rabbit]

Doesn't a Turing machine require an infinite reel of instruction loaded tape?

[iago]

Yes, technically.  You can still design finite state machines on a computer, if you really wanted to, you just might run out of memory. 

All the Turing Machines we did in school were on paper, though, so we never actually ran them, so we didn't have to worry about running out of tape. 

[rabbit]

Aww :\

[Chavo]

My first project requiring the use of a state machine was a lab project where we had to make a 1-dimensional Pong game with a row of LEDs, two push button switches and a few logic chips.  Sound easy? it was. :P

[iago]

Haha, ours was that code I posted in my initial post, which involved 2 switches and 4 or 5 LEDs.  We basically did mouse-like features, double-click, clicking both buttons, holding a button, etc.

Sadly, I don't have the instructions for it anymore, or I could show you. :(