6

アイドル状態から始まり、何らかのイベントに基づいてある状態から別の状態に移行する FSM を作成したいと考えています。私は FSM のコーディングに慣れておらず、Google は役に立ちませんでした。誰かが同じために使用できるCデータ構造を投稿できれば感謝します。

ありがとう、syuga2012

4

7 に答える 7

5

過去に通信事業者向けに有限ステート マシンを実装し、次のように事前設定された構造体の配列を常に使用していました。

/* States */
#define ST_ANY    0
#define ST_START  1
: : : : :

/* Events */
#define EV_INIT   0
#define EV_ERROR  1
: : : : :

/* Rule functions */
int initialize(void) {
    /* Initialize FSM here */
    return ST_INIT_DONE
}
: : : : :

/* Structures for transition rules */
typedef struct {
    int state;
    int event;
    (int)(*fn)();
} rule;
rule ruleset[] = {
    {ST_START, EV_INIT, initialize},
    : : : : :
    {ST_ANY, EV_ERROR, error},
    {ST_ANY, EV_ANY, fatal_fsm_error}
};

fnこれはメモリからのものであるため、関数ポインタが間違って宣言されている可能性があります。基本的に、ステート マシンは関連するステートとイベントを配列で検索し、必要な処理を実行して新しいステートを返す関数を呼び出しました。

ルールの優先度は配列内の位置に依存するため、特定の状態が最初に配置され、ST_ANY エントリが最後に配置されました。最初に見つかったルールが使用されました。

さらに、検索を高速化するために、各状態の最初のルールへのインデックスの配列があったことを覚えています (開始状態が同じすべてのルールがグループ化されました)。

また、これは純粋な C であったことに注意してください。C++ で行うより良い方法があるかもしれません。

于 2009-04-07T14:53:50.613 に答える
2

ここでの答えは非常に複雑に思えます (しかし、それでもなお正確です)。

まず、dmckee の FSM の (操作上の) 定義と、それらがプログラミングにどのように適用されるかが気に入っています。

有限ステート マシンは、有限数の離散状態 (私はペダンティックなことを知っていますが、それでも) で構成され、一般に整数値として表すことができます。c または c++ では、列挙を使用することは非常に一般的です。

マシンは有限数の入力に応答しますが、これはしばしば別の整数値の変数で表すことができます。より複雑なケースでは、構造体を使用して入力状態を表すことができます。

内部状態と外部入力の各組み合わせにより、マシンは次のようになります。

  1. 別の状態に遷移する可能性がある
  2. おそらくいくつかの出力を生成します

だからあなたはプログラムを持っています。それには状態があり、それらの数は有限です。(「電球が明るい」または「電球が暗い」または「電球が消えている」の 3 つの状態。有限です。) プログラムは、一度に 1 つの状態にしかなれません。

たとえば、プログラムの状態を変更したいとします。通常、状態の​​変更をトリガーする何かが発生する必要があります。この例では、ユーザー入力を取得して状態 (たとえば、キーの押下) を判断するのはどうでしょうか。

このようなロジックが必要になる場合があります。ユーザーがキーを押すと:

  1. 電球が「オフ」の場合は、電球を「暗く」します。
  2. 電球が「暗い」場合は、電球を「明るく」します。
  3. 電球が「明るい」場合は、電球を「オフ」にします。

明らかに、「電球を変更する」のではなく、「テキストの色を変更する」など、プログラムで必要なことは何でも行うことができます。開始する前に、状態を定義する必要があります。

したがって、いくつかの疑似 C コードを見てみましょう。

/* We have 3 states. We can use constants to represent those states */
#define BULB_OFF 0
#define BULB_DIM 1
#define BULB_BRIGHT 2

/* And now we set the default state */
int currentState = BULB_OFF;

/* now we want to wait for the user's input. While we're waiting, we are "idle" */
while(1) {
   waitForUserKeystroke(); /* Waiting for something to happen... */

   /* Okay, the user has pressed a key. Now for our state machine */

   switch(currentState) {
      case BULB_OFF:
         currentState = BULB_DIM;
         break;
      case BULB_DIM:
         currentState = BULB_BRIGHT;
         doCoolBulbStuff();
         break;
      case BULB_BRIGHT:
         currentState = BULB_OFF;
         break;
   }
}

そして、出来上がり。状態を変更する簡単なプログラム。

このコードは、現在の状態switchに応じて、ステートメントのごく一部のみを実行します。次に、その状態を更新します。それがFSMの仕組みです。

ここで、次のことができます。

  1. 明らかに、このプログラムはcurrentState変数を変更するだけです。状態が変化したときに、コードでもっと興味深いことをしたいと思うでしょう。このdoCoolBulbStuff()関数は、実際には電球の写真を画面に表示するかもしれません。か何か。

  2. このコードは、キープレスのみを検索します。ただし、FSM (および switch ステートメント) は、ユーザーが入力した内容に基づいて状態を選択できます (たとえば、「O」は、シーケンス内の次のものに進むのではなく、「オフにする」ことを意味します)。

あなたの質問の一部は、データ構造を求めました。

ある人はenum、状態を追跡するために を使用することを提案しました。#definesこれは、私の例で使用した の良い代替手段です。人々は配列も提案してきました - これらの配列は状態間の遷移を追跡します。こちらも使い勝手の良い構造です。

上記を考えると、あらゆる種類の構造 (ツリーのようなもの、配列など) を使用して、個々の状態を追跡し、各状態で何を行うかを定義できます (したがって、「関数ポインターを使用するためのいくつかの提案」 " - その状態で何をすべきかを示す関数ポインタへの状態マップを持っています。)

それが役立つことを願っています!

于 2009-06-08T01:25:50.317 に答える
2

有限ステート マシンは、有限数の離散状態 (私はペダンティックなことを知っていますが、それでも) で構成され、一般に整数値として表すことができます。c または c++ では、列挙を使用することは非常に一般的です。

マシンは有限数の入力に応答しますが、これはしばしば別の整数値の変数で表すことができます。より複雑なケースでは、構造体を使用して入力状態を表すことができます。

内部状態と外部入力の各組み合わせにより、マシンは次のようになります。

  1. 別の状態に遷移する可能性がある
  2. おそらくいくつかの出力を生成します

c の単純なケースは次のようになります

enum state_val {
   IDLE_STATE,
   SOME_STATE,
   ...
   STOP_STATE
}
//...    
  state_val state = IDLE_STATE
  while (state != STOP_STATE){
    int input = GetInput();
    switch (state) {
    case IDLE_STATE:
      switch (input) {
        case 0:
        case 3: // note the fall-though here to handle multiple states
          write(input); // no change of state
          break;
        case 1: 
          state = SOME_STATE;
          break
        case 2:
          // ...
      };
      break;
    case SOME_STATE:
      switch (input) {
        case 7:
          // ...
      };
      break;
    //...
    };
  };
  // handle final output, clean up, whatever

これは読みにくく、次のような方法で複数の関数に簡単に分割できます。

  while (state != STOP_STATE){
     int input = GetInput();
     switch (state) {
     case IDLE_STATE:
       state = DoIdleState(input);
       break;
     // ..
     };
  };

各状態の複雑さは、それ自体の機能に保持されます。

m3rLinEz が言うように、トランジションを配列に保持して、インデックスをすばやく作成できます。関数ポインタを配列に保持して、アクション フェーズを効率的に処理することもできます。これは、大規模で複雑なステート マシンの自動生成に特に役立ちます。

于 2009-06-08T00:50:17.347 に答える
1

正式な定義については、ウィキペディアを参照してください。状態のセットS、入力アルファベットΣ、および遷移関数δを決定する必要があります。最も単純な表現は、Sを整数のセット0、1、2、...、N -1とします。ここで、Nは状態の数であり、Σの場合は整数のセット0、1、2、...です。 。、M -1、ここでMは入力の数であり、δはN行M列の大きな行列です。最後に、 Nビットの配列を格納することにより、受け入れ状態のセットを格納できます。ここで、 i番目のビットは1です。th状態は受け入れ状態であり、受け入れ状態でない場合は0です。

たとえば、ウィキペディアの記事の図3にあるFSMは次のとおりです。

#define NSTATES 2
#define NINPUTS 2
const int transition_function[NSTATES][NINPUTS] = {{1, 0}, {0, 1}};
const int is_accepting_state[NSTATES] = {1, 0};

int main(void)
{
    int current_state = 0;  // initial state
    while(has_more_input())
    {
        // advance to next state based on input
        int input = get_next_input();
        current_state = transition_function[current_state][input];
    }

    int accepted = is_accepting_state[current_state];
    // do stuff
}
于 2009-04-07T14:42:02.857 に答える
1

基本的に、「if」条件と変数を使用して、FSMの現在の状態を格納できます。

例（単なる概念）：

int state = 0;
while((ch = getch()) != 'q'){
    if(state == 0)
        if(ch == '0')
            state = 1;
        else if(ch == '1')
            state = 0;
    else if(state == 1)
        if(ch == '0')
            state = 2;
        else if(ch == '1')
            state = 0;
    else if(state == 2)
    {
        printf("detected two 0s\n");
        break;
    }
}

より洗練された実装では、2次元配列でのストア状態遷移を検討できます。

int t[][] = {{1,0},{2,0},{2,2}};
int state = 0;

while((ch = getch()) != 'q'){
    state = t[state][ch - '0'];
    if(state == 2){
        ...
    }
}
于 2009-04-07T14:42:33.137 に答える
1

AT&T の何人かが、現在は Google に所属し、一般的に使用できる最高の FSM ライブラリの 1 つを作成しました。ここで確認してください。これはOpenFSTと呼ばれます。

それは高速で効率的であり、FSM で実行できる非常に明確な一連の操作を作成して、FSM を最小化したり決定したりして、現実の問題に対してさらに役立つようにしました。

于 2009-06-06T20:26:01.240 に答える
0

FSM が有限ステート マシンを意味し、単純なものが好きな場合は、列挙型を使用して状態に名前を付け、それらを切り替えます。

それ以外の場合は、ファンクターを使用します。stl または boost のドキュメントで凝った定義を調べることができます。

それらは多かれ少なかれオブジェクトであり、たとえば run() と呼ばれるメソッドを持ち、その状態で実行する必要があるすべてを実行します。各状態には独自のスコープがあるという利点があります。

于 2009-04-07T14:47:26.367 に答える