Nested FSM implementation

P

Polomora

Hello.

I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.

I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.

SMC looked promising, however, it doesn't support nested FSMs.

Many thanks,
Paul
 
K

Kenny McCormack

Hello.

I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.

I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.

SMC looked promising, however, it doesn't support nested FSMs.

Many thanks,
Paul

LBJ took the IRT...
 
J

jacob navia

Polomora said:
Hello.

I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.

I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.

SMC looked promising, however, it doesn't support nested FSMs.

Many thanks,
Paul

Acronyms are a plague

if (FSM == "Finite State Machine") {
printf("Off topic in this newsgroup\n");
printf("Use another newsgroup\n");
}
else
{
printf("What is a \"FSM\"\n");
}
 
J

Julian V. Noble

Polomora said:
Hello.

I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.

I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.

SMC looked promising, however, it doesn't support nested FSMs.

Many thanks,
Paul

Think of a deterministic FSM as a 2-dim table. The row labels are
states, the column labels are inputs. The table entries have two
parts: an action and a transition to the appropriate state following
that action.

The FSM must have a place to keep the current state. Before you
enter the FSM you must initialize the state to 0. You also need
a function that translates your input data to a column label. To
get to the appropriate table entry you compute an offset from
the base address:

offset_in_address_units = column# + row# * width

where width is the number of cells in a row.

Perhaps a struct would be the best way to program this, with each
cell holding two function addresses, one for the action and one
for the next state transition. Alternatively you might represent
the FSM as a giant switch construct.

I don't know any elegant way to do this in C. It would probably
be easier in an object-oriented language like C++ where you can
package code with the data structure. I have only done it in Forth
where it was also relatively easy.

You might try to devise a mini-language for constructing FSMs and
implementing its translation to C with YACC.

Once you have done this, however, and represented the FSM as a
function, you can easily embed that function as an action in
another FSM.

Finally, I have an online article on FSMs that mentions some
C software tools that were available several years ago:

http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html

You might try to see whether some of these are still available
before trying to roll your own.
 
R

Rod Pemberton

Julian V. Noble said:
Think of a deterministic FSM as a 2-dim table. The row labels are
states, the column labels are inputs. The table entries have two
parts: an action and a transition to the appropriate state following
that action.

The FSM must have a place to keep the current state. Before you
enter the FSM you must initialize the state to 0. You also need
a function that translates your input data to a column label. To
get to the appropriate table entry you compute an offset from
the base address:

offset_in_address_units = column# + row# * width

where width is the number of cells in a row.

Perhaps a struct would be the best way to program this, with each
cell holding two function addresses, one for the action and one
for the next state transition. Alternatively you might represent
the FSM as a giant switch construct.

Using a struct eliminates any correlation with the data in the FSM table.
Also, alignment issues and padding problems may slow the code down. I would
recommend creating two 2-dim tables ("arrays" in C).
Finally, I have an online article on FSMs
http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html

I don't know any elegant way to do this in C. It would probably
be easier in an object-oriented language like C++ where you can
package code with the data structure. I have only done it in Forth
where it was also relatively easy.

I found your article to be interesting, so here is a Public Domain C version
of the example on your web-page. Unfortunately, in C there is no portable
way to get a character without echoing it to the screen. C always combines
FORTH's KEY and EMIT. Since this is necessary for your FSM example, the
code has some DOS specific code which should be easy to modify for other
OS's such as Linux.

/* port of a FORTH Finite State Machine by JV Noble */
/* C version by Rod Pemberton */
/* released to the Public Domain */
/* September 8th, 2006 */
#if 0
http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h> /* for non-echo get() */

void getstate(unsigned char *ch)
{
/* These two commented out are ISO, */
/* but they echo which we don't want... */
/* *ch=getchar(); */
/* scanf("%c",ch); */

/* non-ISO, non-echo getc() */
/* this will need to be modified */
/* to work for non-DOS systems */
while(!kbhit());
*ch=getch();
if(*ch==0x1a) /* ctrl-Z for EOF */
exit(EXIT_SUCCESS);
}

void echo(unsigned char ch)
{
printf("%c",ch);
fflush(stdout);
}

int other(unsigned char ch)
{
int result=0;

/* empty */
return(result);

}

int digit(unsigned char ch)
{
int result=0;

/* isdigit() is fine too... */
if(strchr("0123456789",ch)!=NULL)
result=1;
return(result);
}

int minus(unsigned char ch)
{
int result=0;

if(ch=='-')
result=1;
return(result);
}

int dp(unsigned char ch)
{
int result=0;

if(ch=='.')
result=1;
return(result);
}


#define MAXSTATES 3
#define MAXINPUTS 4

int main(void)
{
unsigned char state=0,input=0,mystate;

/* RP chose to use two arrays instead */
/* of a struct with pointers to functions */
/* to keep the initialization similar to */
/* JV Noble's FORTH FSM tables */

unsigned char action[MAXSTATES][MAXINPUTS]
={
{'X','E','E','E'},
{'X','E','X','E'},
{'X','E','X','X'} /* no comma */
};
unsigned char transition[MAXSTATES][MAXINPUTS]
={
{0,1,1,2},
{1,1,1,2},
{2,2,2,2} /* no comma */
};

while(1)
{
getstate(&mystate);
input=0*other(mystate)
+1*digit(mystate)
+2*minus(mystate)
+3*dp(mystate);
switch(action[state][input])
{
case 'X': /* no action */
break;
case 'E': echo(mystate);
break;
}
state=transition[state][input];
}
}


Sincerely,

Rod Pemberton
 
W

websnarf

Polomora said:
I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.

I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.

SMC looked promising, however, it doesn't support nested FSMs.

I've never used any kind of infrastructure for implementing a finite
state machine (though I have heard of Teja). I just usually code them
up directly. But it seems to me that you can always have multiply
declared states, and transition through them easily, and that nesting
should not be a problem. I would say that an infrastructure that
didn't allow nesting is pretty weak and not really adding any value at
all versus just straight coding it (presumably a useful infrastructure
would make the nesting itself comparably useful.)

Unfortunately, I don't really have anything insightful to add, except
to say -- is just coding it directly really that bad?
 
E

EventHelix.com

I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.

I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.

SMC looked promising, however, it doesn't support nested FSMs.

I would recommend moving over to C++. The following articles would
help:

http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top