State machines, is this topic taught any more?

[ehughes]

To answer the original question.  Yes.   I teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course) as well as to junior engineers in my company.

What I see as the biggest oversight in implementations is the lack of guards when transitioning between states.   Regardless of how the state machine is implemented in code (function pointer table,   switch/case),    I never allow a state variable to be directly modified.   There is always a singular function that (i.e. TransitionToState(.....))  that accepts the new state, checks to see if it valid, implements any logic during the transition, etc.


Seeing things like

Code: [Select]

State +=3 ;// Move to the state that checks the dilthium interposer before enable IPS conduits)
scare me!

I personally like

Code: [Select]

WarpDriveStateTransition(CHECK_DILITHIUM_INTEPOSER);

[tggzzz]

To answer the original question.  Yes.   I teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course) as well as to junior engineers in my company.

What I see as the biggest oversight in implementations is the lack of guards when transitioning between states.   Regardless of how the state machine is implemented in code (function pointer table,   switch/case),    I never allow a state variable to be directly modified.   There is always a singular function that (i.e. TransitionToState(.....))  that accepts the new state, checks to see if it valid, implements any logic during the transition, etc.


Seeing things like

Code: [Select]

State +=3 ;// Move to the state that checks the dilthium interposer before enable IPS conduits)
scare me!

I personally like

Code: [Select]

WarpDriveStateTransition(CHECK_DILITHIUM_INTEPOSER);

The other major advantage of TransitionToState() functions is that they can log the new state. If the received events are also logged, then you have the basis for a very powerful and high-level debugging strategy.

That's invaluable:

• during design to see what's happening and for unit tests
• during integration, where you can see what events the other bugger's code is sending to you
• during comissioning, where you can see what events the other company's product is sending to you
• during lawsuits, since you can prove the other company/bugger is at fault

Seriously.

[ralphrmartin]

There are many structured programming design patterns that are very well-suited for FSMs, with 2D arrays of function pointers being an excellent example. One dimension's index is the state, the other dimension's is the event.

That's certainly one way of doing it, and a neat way of doing it, if your supports functions as first class values.

But it's still nowhere as easy for undergarduates to grasp as
GOTO stateN...

[tggzzz]

There are many structured programming design patterns that are very well-suited for FSMs, with 2D arrays of function pointers being an excellent example. One dimension's index is the state, the other dimension's is the event.

That's certainly one way of doing it, and a neat way of doing it, if your supports functions as first class values.

But it's still nowhere as easy for undergarduates to grasp as
GOTO stateN...

There are other neat, and in some ways better, design patterns which don't require functions as (exposed) first class values. The point is to think at a high level, and to find a way to express those thoughts in a structured form in whatever language you are using.

With FSMs, a key test is when (not if) there is a bug or enhancement, is it easy:

• to understand where the change must be made?
• to know that the change will not affect other unrelated use-cases

Using gotos and nested if-the-else statements both completely fail that test.

[NorthGuy]

What are the odds? I posted this on stackoverflow.com a day before OP started this thread.

I wouldn't qualify this as a state machine. The state machine is basically a function which calculates new state based on the old state and the input:

state = state_machine (state, input)

Even though your task formally qualifies as a Mealy state machine, it isn't programmed like one. I'll take a liberty to pull the relevant code from the stackoverflow (comments mine):

Code: [Select]

void cat_to_dog(FILE *in, FILE *out)
{
    int ch;

    ch = fgetc(in); // blocking call
    while (ch != EOF) {
        if (ch != 'c') {
            fputc(ch, out);
            ch = fgetc(in);
            continue;
        }

        ch = fgetc(in); // blocking call
        if (ch == EOF) {
            fputc('c', out);
            break;
        } else
        if (ch != 'a') {
            fputc('c', out);
            continue;
        }

        ch = fgetc(in); // blocking call
        if (ch == EOF) {
            fputc('c', out);
            fputc('a', out);
            break;
        } else
        if (ch != 't') {
            fputc('c', out);
            fputc('a', out);
            continue;
        }

        fputc('d', out);
        fputc('o', out);
        fputc('g', out);

        ch = fgetc(in); // blocking call
    }
}
Here you do not have any variables representing the state. Even the state does exist, it is maintained implicitly. You have a number of blocking calls. During such calls, if there's no data, the OS will abandon your thread until the new data is ready. During this "out" time, the state of your machine is implicitly remembered by OS as an address where to return - the address of one of your numerous blocking calls. This may be convenient, but your program now requires a multi-threading OS. Your program is also unable to do other simple things, such as saving the state of the state machine for future use.

Traditional implementation of a state machine would contain an explicit variable defining the state, along the functions dealing with the state. For example:

Code: [Select]

void dogger_init(dogger_state *s);
void dogger_update(dogger_state *s, char c);
void dogger_fin(dogger_state *s);
Here, the "init" function initializes the state variable, the "update" function is the state machine itself which takes the state and the input and moves the state machine to the next state, and the "fin" function does the final housekeeping.

When it is organized in such way, you do not need to block the thread waiting for the next char. The state machine does the calculation and returns back. You now can have literally thousands of independent active state machines at the same time. You can also save the state of any machine and then restart it from the given state.

Of course, if you wish you can linearize the execution, such as:

Code: [Select]

void main()
{
  char c;
  char *p = "dog eat cat\n";
  dogger_state s;
 
  dogger_init(&s);
   
  while (c = *p++) {
    dogger_update(&s,c);
  }
 
  dogger_fin(&s);
}
The biggest problems is to come up with good states and effective transitions. The state is usually a number, but in your case, the last two characters fully represent the state, so you can come up with the following state variable type:

Code: [Select]

typedef struct {
  char a, b;
} dogger_state;
where "b" is the last character, and "a" is one before that.

With such state, the implementation is simple:

Code: [Select]

void dogger_init(dogger_state *s) {
  s->a = 0;
  s->b = 0;
}

void dogger_update(dogger_state *s, char c) {
 
  // check for "cat" and replace if found
  if (c=='t'&&s->b=='a'&&s->a=='c') {
    s->a = 'd';
    s->b = 'o';
    c = 'g';
  }
 
  // send out the pending character
  if (s->a) putchar(s->a);
 
  // advance the state
  s->a = s->b;
  s->b = c;
}

void dogger_fin(dogger_state *s) {
  dogger_update(s,0);
  dogger_update(s,0);
}
Putting it all together:

Code: [Select]

#include <stdio.h>
#include <stdint.h>

typedef struct {
  char a, b;
} dogger_state;

void dogger_init(dogger_state *s) {
  s->a = 0;
  s->b = 0;
}

void dogger_update(dogger_state *s, char c) {
 
  // check for "cat" and replace if found
  if (c=='t'&&s->b=='a'&&s->a=='c') {
    s->a = 'd';
    s->b = 'o';
    c = 'g';
  }
 
  // send out the pending character
  if (s->a) putchar(s->a);
 
  // advance the state
  s->a = s->b;
  s->b = c;
}

void dogger_fin(dogger_state *s) {
  dogger_update(s,0);
  dogger_update(s,0);
}

void main()
{
  char c;
  char *p = "dog eat cat\n";
  dogger_state s;
 
  dogger_init(&s);
   
  while (c = *p++) {
    dogger_update(&s,c);
  }
 
  dogger_fin(&s);
}
And the end result:

Code: [Select]

$./dogger
dog eat dog
$

[Nominal Animal]

guards when transitioning between states.

It is nice to see there are still those who teach proper engineering principles with software 

Code: [Select]

State +=3 ;// Move to the state that checks the dilthium interposer before enable IPS conduits)

That is scary to see, but not as seppuku-inducing as what you typically see in real-life software projects:

Code: [Select]

// State = 23;
// 20080323 devnam1: Fix PR#20121.
// State += 5;
// 20101130 devnam2: Fix #PR30115 and #PR30121. 
State += 3;

I wouldn't qualify this as a state machine.

Then you're using the term wrong. It is a classic state machine, just described using a flowchart.

The state machine is basically a function which calculates new state based on the old state and the input:

No. You are confusing finite state machines as a model of computation, and design patterns used for implementing state machines. (Exactly the sort of thing I was complaining about earlier; the gap between software engineering and information technology.)

If you can't parse the state machine the flowchart describes, I can write it as a state table for you.

[brucehoult]

There are many structured programming design patterns that are very well-suited for FSMs, with 2D arrays of function pointers being an excellent example. One dimension's index is the state, the other dimension's is the event.

That's certainly one way of doing it, and a neat way of doing it, if your supports functions as first class values.

But it's still nowhere as easy for undergarduates to grasp as
GOTO stateN...

Another problem with an actual 2D array is that if there are a large number of states and a large number of events then it's likely that the array is quite sparse (or at least, most of the entries are some kind of default or error state). In this case it's better to hash the state and event together and use a 1D array about the same size as the number of valid combinations (or a little larger), and a chaining scheme for collisions. It might take a dozen more instructions, but that's unlikely to be a problem.

[Nominal Animal]

It might be interesting to compare different implementations or descriptions of a simple state machine, say an alarm clock implemented on a small microcontroller, say with four buttons: alarm, set, +, and -; no snooze functionality.

It is interestingly intertwined with the hardware as well. Hardware or software debouncing for the buttons? Interrupts or timing/counting/something else for blinking the digits when editing? Accelerated advance when + or - button is kept depressed long enough? And so on. Might be a good exercise for those studying FSMs; also mix in a bit of user interface design basics.

[NorthGuy]

The state machine is basically a function which calculates new state based on the old state and the input:

No. You are confusing finite state machines as a model of computation, and design patterns used for implementing state machines. (Exactly the sort of thing I was complaining about earlier; the gap between software engineering and information technology.)

What you quoted from my post is the definition of what the finite sate machine is, and is not related to any implementations. How can we possibly discuss things if we do not have a definition? If you don't like my definition, come up with your own. Although it's defined pretty well in mathematics - look, for example, here (scroll a little bit down to "Formal Definition"):

https://en.wikipedia.org/wiki/Mealy_machine

So, what is the definition of the finite state machine in your eyes?

[bsfeechannel]

I had an unexpected experience today, I was handing over a project to half a dozen reasonably experienced developers which uses a state machine to orchestrate and synchronise its tasks. Only one of them knew what a state machine was, so I ended up spending half the meeting explaining the concept, not the easiest of tasks if you’re not prepared.

Admittedly this isn’t an embedded system, it’s a big server-side database manipulation task, but I’d still expect any software developer to have at least heard of state machines, or are state machines outside of embedded systems a bit too old school nowadays?

Would it be easier if the concept were introduced taking regex as a starting point?

[westfw]

are state machines outside of embedded systems a bit too old school nowadays?

FSMs are taught in any (decent) introductory CS course

I dunno.  It's a "data structures and algorithms" topic, maybe.  2nd year or so?
It's barely mentioned in Sedgewick, and only in conjunction with searching.
I had it (~1980) as part of the digital logic and/or computer architecture class (very hardware oriented), and again as part of the Compiler class (WRT "parsing.")  These days it ought to show up in networking internals classes, too.

"Automata Theory" tends to be a grad class, very mathematical and theory-based.
(ie https://online.stanford.edu/courses/soe-ycsautomata-automata-theory)

I think most students would be lucky to have done one example (the infamous "traffic light"), and have never seen it show up as a general purpose tool.  FSMs are sort of "unclean" compared to modern tools like graphs and trees - the concept is simple, but there's a lot of complexity in setting things up.  Also, they're hard to document internal to softare (yeah, state diagrams are swell.  Til you try to do one in ASCII art), and they can be a pain to debug.  Software FSMs can easily suffer from a lot of "sloppiness" in terms of implementing things in a particular state that ought to be mutiple states, and WRT integrating some sort of "clock."


(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding."  Sigh.
And even if you learned it, you probably don't remember it until after you've had to actually use it a few times.)

I teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course)

Neither is ""outside" of embedded systems"

I took an EDX course from UT 6.02x Embedded Systems.
One of the labs was indeed to design a finite state machine for a traffic lights

Heh.  I was in that class (or the 1st one, anyway.)  IIRC, that lab was quite the disaster for a lot of the participants.  Generated MUCH discussion.

[Nominal Animal]

So, what is the definition of the finite state machine in your eyes?

See e.g. the Wikipedia finite-state machine article. It has a pretty good definition, and also differentiates between the model itself, and its various representation/implementation methods.

A Mealy machine is just one specific model with an associated representation (the model is restricted to fit a specific representation).  Not all finite-state machines are Mealy machines, even when all Mealy machines are finite-state machines.

[Nominal Animal]

(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding."  Sigh.

Dammit, that's exactly what I was trying to say above, with software engineering and information technology.  Me fail English .

[tggzzz]

(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding."  Sigh.

Dammit, that's exactly what I was trying to say above, with software engineering and information technology.  Me fail English .

No, you don't fail English: your statements are easy to understand. I may disagree with them, but that is a different issue

[Nominal Animal]

I may disagree

Believe or not, but I actually appreciate that a lot (from everyone, not just you), when the differing viewpoint/reasoning is shown.  I'd often miss my own errors otherwise, and I'd rather admit to and fix my own errors, than lead others astray.  That also means that I can be quite aggressive when I see claims that might lead others astray; I can't usually just let them be. 

Anyway, here's the same cat-to-dog state machine description in table form. This one is suitable for use with a Mealy machine. 

Code: [Select]


 State │ Description   │ Input │ Action                │ Next state
═══════╪═══════════════╪═══════╪═══════════════════════╪═══════════════
 INIT  │ Initial state │ EOF   │                       │ END
       │               ├───────┼───────────────────────┼───────────────
       │               │ 'C'   │                       │ C
       │               ├───────┼───────────────────────┼───────────────
       │               │       │ Output input          │ INIT
───────┼───────────────┼───────┼───────────────────────┼───────────────
 C     │ Have 'C'      │ EOF   │ Output 'C'            │ END
       │               ├───────┼───────────────────────┼───────────────
       │               │ 'A'   │                       │ CA
       │               ├───────┼───────────────────────┼───────────────
       │               │ 'C'   │ Output 'C'            │ C
       │               ├───────┼───────────────────────┼───────────────
       │               │       │ Output 'C' and input  │ INIT
───────┼───────────────┼───────┼───────────────────────┼───────────────
 CA    │ Have "CA"     │ EOF   │ Output "CA"           │ END
       │               ├───────┼───────────────────────┼───────────────
       │               │ 'T'   │ Output "DOG"          │ INIT
       │               ├───────┼───────────────────────┼───────────────
       │               │ 'C'   │ Output "CA"           │ C
       │               ├───────┼───────────────────────┼───────────────
       │               │       │ Output "CA" and input │ INIT
───────┼───────────────┼───────┼───────────────────────┼───────────────
 END   │ End of input  │

If you use UTF-8, such tables can be included in comments, if you use a fixed-size font when writing code.

I do not have a strong opinion on what form or what tools are best for describing state machines, as I always pick on a case-by-case basis.  I used the flowchart at SO simply because I thought it would be easiest for new programmers to understand.  In general, the table forms are easier to maintain.  With a large number of states, using visualization tools like Graphviz that can be used to generate nice graphs from text, make it easier to get an overall picture of the complexity, and proper context when contemplating changes.

For an FSM that implements say a menu system in C on a microcontroller, I use a structs, as GCC allows constructing it at compile time in read-only memory. You do need to forward-declare the states (static const struct menustate  menu_foo; before referring to it via &menu_foo), but with a little care, the end result is maintainable.

[tggzzz]

I may disagree

Believe or not, but I actually appreciate that a lot (from everyone, not just you), when the differing viewpoint/reasoning is shown.  I'd often miss my own errors otherwise, and I'd rather admit to and fix my own errors, than lead others astray.  That also means that I can be quite aggressive when I see claims that might lead others astray; I can't usually just let them be. 

Join the club.

I do not have a strong opinion on what form or what tools are best for describing state machines, as I always pick on a case-by-case basis. 

Me too. Many techniques can be used.

I've used "event = thread.yieldUntilOrTimeout(setOfInterestingEvents, timeoutMs); process(event);" "continuation-style" code in the past. That does read like a flowchart!

I used the flowchart at SO simply because I thought it would be easiest for new programmers to understand.  In general, the table forms are easier to maintain.  With a large number of states, using visualization tools like Graphviz that can be used to generate nice graphs from text, make it easier to get an overall picture of the complexity, and proper context when contemplating changes.

One consequence of using a flowchart is that the FSM nature of the code is implicit rather than explicit. Another is that it is less suited to event-driven programming and more difficult to integrate with other activities. Beginners seem to have no difficulty understanding for( ; ; ) superloops, and how event driven code fits into that.

[NorthGuy]

So, what is the definition of the finite state machine in your eyes?

See e.g. the Wikipedia finite-state machine article. It has a pretty good definition, and also differentiates between the model itself, and its various representation/implementation methods.

Ok. Here's the definition from the page you quoted:

Code: [Select]

A deterministic finite state machine or acceptor deterministic finite state machine is a quintuple,

"Sigma"  is the input alphabet (a finite, non-empty set of symbols).
"S" is a finite, non-empty set of states.
"S0" is an initial state, an element of S.
"Selta"  is the state-transition function: Delta : S × Sigma -> S
"F" is the set of final states, a (possibly empty) subset of S.
Doesn't look much different from the Mealy page, but anyway:

Looking at the code you wrote for your cat->dog machine, can you point out where is the "set of states" and where is the "state-transition function"?

A Mealy machine is just one specific model with an associated representation (the model is restricted to fit a specific representation).  Not all finite-state machines are Mealy machines, even when all Mealy machines are finite-state machines.

Is your cat->dog machine Mealy?

[KaneTW]

are state machines outside of embedded systems a bit too old school nowadays?

FSMs are taught in any (decent) introductory CS course

I dunno.  It's a "data structures and algorithms" topic, maybe.  2nd year or so?
It's barely mentioned in Sedgewick, and only in conjunction with searching.
I had it (~1980) as part of the digital logic and/or computer architecture class (very hardware oriented), and again as part of the Compiler class (WRT "parsing.")  These days it ought to show up in networking internals classes, too.

"Automata Theory" tends to be a grad class, very mathematical and theory-based.
(ie https://online.stanford.edu/courses/soe-ycsautomata-automata-theory)

I think most students would be lucky to have done one example (the infamous "traffic light"), and have never seen it show up as a general purpose tool.  FSMs are sort of "unclean" compared to modern tools like graphs and trees - the concept is simple, but there's a lot of complexity in setting things up.  Also, they're hard to document internal to softare (yeah, state diagrams are swell.  Til you try to do one in ASCII art), and they can be a pain to debug.  Software FSMs can easily suffer from a lot of "sloppiness" in terms of implementing things in a particular state that ought to be mutiple states, and WRT integrating some sort of "clock."


(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding."  Sigh.
And even if you learned it, you probably don't remember it until after you've had to actually use it a few times.)

I teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course)

Neither is ""outside" of embedded systems"

I took an EDX course from UT 6.02x Embedded Systems.
One of the labs was indeed to design a finite state machine for a traffic lights

Heh.  I was in that class (or the 1st one, anyway.)  IIRC, that lab was quite the disaster for a lot of the participants.  Generated MUCH discussion.

In my university state machines are a 2nd semester mandatory class for Bachelor CS, with advanced automata theory being a 4th semester+elective. FSMs for embedded systems are taught in 4th semester+ electives, too.

[westfw]

In my university state machines are a 2nd semester mandatory class for Bachelor CS

A whole class?  Software State Machines?Do you happen to have a class syllabus and/or textbook reference handy?I'd be interesting looking at educational material that is more in-depth than The Traffic Light while being less theoretical than the advanced FSA classes I've seen...

[Nominal Animal]

Ok. Here's the definition from the page you quoted:

No, that's the formal definition of the mathematical model that can represent any finite-state machine. Here's the actual definition, shortened a bit:

Finite-state machine is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition.

Doesn't look much different from the Mealy page

Well of course the mathematical definition is the same, for chrissakes! What part of all Mealy machines are finite-state machines did you miss?

The flowchart describes an implementation of a finite-state machine. I chose a flowchart, rather than a table, because I thought that at StackOverflow new programmers would find it much easier to convert a flowchart to code. (Do note that I forgot to add an edge from "Output D O G" to the top node.)

To convert it to a flowchart where each state is clearly delineated, I would have to duplicate the diamond corresponding to the char = C test twice (to the two states below it). In an implementation, the single test suffices, as the transition caused by that test is always the same, and it nicely simplifies the code as well. Nevertheless, repeating that test twice more, the three non-final states would be vertically stacked, with the fourth final Done state on the right side.

If that is your objection, I'd be inclined to agree, and be more than happy to fix the flowchart, and add the states as say shaded background areas.

Mathematically, the input alphabet set Σ is the set of values C fgetc() function may return. Of this set, values EOF, 'c', 'a', and 't' are used in determining the appropriate action and state transition, and all other values use a common action and state transition.

The set of states S has three states: Initial state, C state, and C A state. The initial state S₀ should be obvious. There is one final state in F , Done . The transition function δ(state, input) can be described thus:
δ(Initial, EOF) = Done
δ(Initial, 'c') = C
δ(Initial, other) = Initial
δ(C, EOF) = Done
δ(C, 'a') = C A
δ(C, 'c') = C
δ(C, other) = Initial
δ(C A, EOF) = Done
δ(C A, 't') = Initial
δ(C A, 'c') = C
δ(C A, other) = C

In Mealy machine terms, the output alphabet Λ is the input set Σ except for EOF. The output function G: S×Σ can be defined as
G(Initial, EOF) = Nothing
G(Initial, 'c') = Nothing
G(Initial, other) = other
G(C, EOF) = 'c'
G(C, 'a') = Nothing
G(C, 'c') = 'c'
G(C, other) = 'c'
G(C A, EOF) = 'c' 'a'
G(C A, 't') = 'd' 'o' 'g'
G(C A, 'c') = 'c'
G(C A, other) = 'c' 'a'

I was not trying to be snide, when I said that if you have difficulty reading the flow chart into a finite-state machine, I could show the state table also. Like tggzzz wrote, it is not obvious.

Looking at the code you wrote for your cat->dog machine, can you point out where is the "set of states" and where is the "state-transition function"?

The model the code implements is a finite state machine. It does not mean that the code must contain identifiable elements that correspond to the mathematical description.

This is exactly what I mean by there being a gap between "coding" and "computer science".

The model the code implements is a finite-state machine. The design pattern it uses to do so is a simple loop; not something often used for finite-state machines. Yet, that does not mean the code does not implement a finite-state machine.

Is your cat->dog machine Mealy?

So funny, ha-ha. Only if your definition of a Mealy machine allows the output function G to output more than one symbol at a time.

[Nominal Animal]

Would this diagram work better than my earlier one?

Especially considering new programmers, would this one be easier to understand and implement?

White rounded rectangles are states, and the gray rounded rectangle is the final state. I didn't name the states, as there are just three. The "Read char" label reminds new programmers to read a new character.
Yellow rectangles name input characters. Arrows with a red head are state transitions. Blue rounded rectangles are output actions. The intent is to be intuitive even for those who are not used to reading such flowcharts.

[KaneTW]

In my university state machines are a 2nd semester mandatory class for Bachelor CS

A whole class?  Software State Machines?Do you happen to have a class syllabus and/or textbook reference handy?I'd be interesting looking at educational material that is more in-depth than The Traffic Light while being less theoretical than the advanced FSA classes I've seen...

Not quite a whole class, but a major part. I should note it focuses more on DFA/NFAs in the context of languages. https://verify.rwth-aachen.de/fosap10/ -- German only unfortunately.

[JPortici]

Would this diagram work better than my earlier one?

Is there a software that helps you to generate flowcharts like this without doing everything by hand?

[nfmax]

A comment: when coding a state machine, the current state may be represented either explicitly by a specific, dedicated variable, or implicitly, by the program counter. The software will be more maintainable (=easier for humans to read and understand) using explicit state storage.

[tggzzz]

Would this diagram work better than my earlier one?

Is there a software that helps you to generate flowcharts like this without doing everything by hand?

If you mean "draw", then search for UML StateCharts and similar.

If you mean "reverse engineer" from code, good luck.