4. Automaten

Automaten

  • P

    sowas von hand zu basteln kann ziemlich frickelig werden 😉
    es gibt tools, die aus FSMs C code erzeugen können:
    http://legacy.imatix.com/html/libero/index.htm
    http://www.nunnisoft.ch/nunnifsmgen/
    🙂

    0
  • M

    Hallo CStoll,

    erstmal Danke für die schnelle Antwort.

    Genau das meinte ich mit

    Wobei es für jeden Zustand natürlich mehrere Einträge geben kann.

    also ein Zustand hat 0...n Folgezustände. Hab mich unglücklich ausgedrückt

    Was ich nicht verstehe ist.

    (Pointer auf andere Zustände - einer für jede mögliche Eingabe)

    sollte jeder Zustand für jeden Folgezustand einen Pointer haben, also wenn ein Zustand n Folgezustände bestitzt hat man n Pointer.
    Wäre nich sehr gut, oder?

    Gruß, mdoemli

    0
  • M

    Hallo pale dog,

    mhh klingt interessant, aber mach sowas doch immer ganz gerne selbst. Werds mir
    aber mal anschauen.

    Merci

    0
  • C

    mdoemli schrieb:

    Hallo CStoll,

    erstmal Danke für die schnelle Antwort.

    Genau das meinte ich mit

    Wobei es für jeden Zustand natürlich mehrere Einträge geben kann.

    also ein Zustand hat 0...n Folgezustände. Hab mich unglücklich ausgedrückt

    rein technisch hat jeder Zustand genau n Folgezustände (die teilweise übereinstimmen können) 😉 (du mußt mit einer beliebigen Eingabefolge rechnen - notfalls verlinkst du ungültige Eingaben auf einen Fehler-Zustand).

    Was ich nicht verstehe ist.

    (Pointer auf andere Zustände - einer für jede mögliche Eingabe)

    sollte jeder Zustand für jeden Folgezustand einen Pointer haben, also wenn ein Zustand n Folgezustände bestitzt hat man n Pointer.
    Wäre nich sehr gut, oder?

    Du kannst das natürlich noch etwas optimieren, indem du mehrfach auftretende Folgezustände zusammenfasst - aber das erhöht dann den benötigten Rechenaufwand und die Komplexität. Aber sehr weit runteroptimieren wirst du das nicht können - du brauchst auf jeden Fall für jede Kante im Automaten den nötigen Speicherplatz für einen Pointer (und eventuell für eine Liste der betroffenen Eingabewerte).

    //primitive Lösung
int input_size;//Größe der Eingabemenge

struct node
{
  //Hilfsvariablen für Ausgabe/Akzeptanz/whatever
  struct node** next;//=malloc(input_size*sizeof(node*));
};

...
struct node* aktuell = ...;
...
while(!ende)
{
  ...
  aktuell = aktuell->next[input];
}

//etwas kompakter, aber aufwendiger
struct node;
struct edge
{
  char* values;
  struct node* target;
}

struct node
{
  //Hilfsvariablen
  int edge_count;
  struct edge* edges;//=malloc(edge_count*sizeof(edge));
};

struct node error_state = {...,0};

struct node* next_state(struct node* akt,char input)
{
  for(int i=0;i<akt->edge_count;++i)
    if(strchr(akt->edges[i].values,input)!=NULL) return akt->edges[i].target;
  return &error_state;
}

...
struct node* aktuell = ...;
...
while(!ende)
{
  ...
  aktuell = next_state(aktuell,input);
}
    0
  • M

    mhh, raviniert. Wenn ich das richtig verstanden habe baust du den Automaten als eine Art verketteter Listen auf.
    Das was ich dabei nicht möchte ist, dynamisch speicher zu allozieren, da ich auf einer MCU arbeite und deshalb ist das mit dynamischen Speicher so eine Sache.

    Auf jedenfall bringt mich das schon weiter.

    Mein Ansatz war:
    1. Zuerst alle Zustände herauszufinden die eingenommen werden können
    2. Nun alle Möglichen Events aufschreiben und den Automaten aufzeichnen und eine Startkonfiguration (Zustand + Event + nächster Zustand) festlegen.
    3. Alle Zuständsübergänge sollen per Tabelle über Funk geladen werden können.
    Als Beispiel:
    Programm ist in Zustand A und wechselt aufgrund eines Events in C.
    Nun soll man das zur Laufzeit so konfigurieren können, dass bei dem gleichen Event z.B. nicht mehr in Zustand C, sondern in Zustand Z gewechselt wird.

    Deshalb ist ja die Menge der Zustände und Events vor Compilezeit fest und somit
    ließe sich ja ein malloc vermeiden. Deshalb war mein erster Ansatz eben ein
    Struktur-Array, wobei jede Struktur aus einem Zustand und einem Zeiger der auf eine 2-D-Matrix verweist, besteht. Aber so richtig weiß ich nicht wie ich anfangen soll.

    Gruß, mdoemli

    0
  • C

    Wenn die Menge der möglichen Eingabewerte bzw. die Anzahl der Kanten konstant ist, kannst du den Speicher natürlich auch zur Compilezeit anlegen:

    //Modifikation Variante 1:
struct node
{
  ...
  int next[input_size];//Index im Array 'automat'
};

struct node automat[] =
{
  {...,{1,2,1,...}}
  {...}
  ...
};

...
aktuell = automat + aktuell->next[input];

//Modifikation Variante 2:
struct edge
{
  char* values;
  int target;//index im Array 'state'
} next[] =
{
  {"abc",1},
  {"def",2},
  ...
};

struct node
{
  ...
  int fist_edge,edge_count;//Index und Anzahl im Array 'next'
} state[] =
{
  {...,0,2},
  {...,2,3},
  ...
}, error_state = {...,0,0};

struct nod* next_state(struct node* akt, char input)
{
  for(int i=0;i<akt->edge_count;++i)
    if(strchr(next[akt->first_edge+i].values,input)!=NULL) return state+next[akt->first_edge+i].target;
  return &error_state;
}

    (in der zweiten Variante wird es allerdings etwas aufwendiger, wenn du den Übergang für (z.B.) Eingabe 'a' in Zustand 0 später umbiegen willst)

    0
  • M

    Super!!!
    Werd mir das jetzt nochmal genauer überlegen und ein bißchen zeichnen.
    Vielen Dank für die Hilfe!!!!!

    Gruß, mdoemli

    0
  • P

    mdoemli schrieb:

    Deshalb war mein erster Ansatz eben ein
    Struktur-Array, wobei jede Struktur aus einem Zustand und einem Zeiger der auf eine 2-D-Matrix verweist, besteht. Aber so richtig weiß ich nicht wie ich anfangen soll.

    etwa so:

    // maximal mögliche übergänge
#define MAX_TRANSITIONS 10

// struct für einen übergang
struct transition
{
   int event;           // bei deisem ereignis
   int new_state;       // in diesen zustand wechseln
   void (*func)(void);  // und diese funktion aufrufen
};

// ein tabelleneintrag
struct fsm_tableentry
{
   struct transition trans[MAX_TRANSITIONS];
};

// tabelle für die ganze fsm
// array-index ist aktueller zustand
struct fsm_tableentry table[] =
{
   {1,1,f1, 2,2,f2, -1},  // z0: bei ev1 nach z1 wechseln und f1 aufrufen, bei ev2 nach z2 wechseln und f2 aufrufen  
   {7,0,f3, -1},          // z1: bei ev7 nach z0 wechseln und f3 aufrufen 
   {19,1,f4, -1},         // z2; bei ev19 nach z1 wechseln und f4 aufrufen
};

// alles abklappern
int new_state (int state, int event)
{
   int s;
   for (s=0; s<MAX_TRANSITIONS; s++)
   {
      struct transition *p = &table[state].trans[s];
      // am ende angekommen? dann raus
      if (p->event == -1)
         break;
      // übergang gefunden?
      if (p->event == event)
      {
         // funktion aufrufen
         p->func();
         // und neuen zustand zurückgeben
         return p->new_state;
      }
   }
   // keine änderung, zustand beibehalten
   return state;
}

    (nicht ausprobiert, wahrscheinlich buggy)
    🙂

    0
  • M

    hallo pale dog,

    sieht auch sehr gut aus. werd euch dann meine endgültige lösung noch mitteilen.

    gruß, mdoemli

    0
  • M

    Also hab mich jetzt für diesen Ansatz entschieden

    //transition table
typedef struct {
  BYTE  subState;
  BYTE  event;
  BYTE  nextState;
} TRANS_TABLE;

//main states
typedef struct {
  BYTE         st_ID;
  TRANS_TABLE *ttPointer;
} STATE_TABLE;

//current state
typedef struct {
  STATE_TABLE *stPointer;
  BYTE         currentSubState;
} CURRENT_TABLE;

extern TRANS_TABLE    transTable[MAX_TRANSITIONS];
extern STATE_TABLE    stateTable[MAX_STATES];
extern CURRENT_TABLE  currentTable;

    Da viele Events über Interrupts eintreten werde ich noch einen Event-Handler dazu implementieren.
    In der Struktur TRANS_TABLE weiß ich noch nicht ob ich die dazugehörigen Aktionen über einen Funktionszeiger oder über einen switch realisiere.
    CURRENT_TABLE dient dazu um den aktuellen Zustand und Subzustand zu halten und STATE_TABLE enthält alle möglichen Zustände.
    Zur Laufzeit ladbar ist die Struktur TRANS_TABLE.

    Also nochmals vielen Dank für eure Hilfe.

    Gruß, mdoemli

    0
Anmelden zum Antworten