イベント駆動型有限状態マシン

計算において、有限状態マシン(FSM) は、ある状態から別の状態への遷移がイベントまたはメッセージによってトリガーされる場合、イベント駆動型です。これは、有限状態マシンという用語の構文解析理論の起源 (マシンが文字またはトークンを消費すると説明される) とは対照的です。

多くの場合、これらのマシンは、大規模なアプリケーションの一部として相互に通信するスレッドまたはプロセスとして実装されます。たとえば、通信プロトコルはほとんどの場合、イベント駆動型の有限状態マシンとして実装されます。

このコードは、非常に基本的なカーラジオ システムのステート マシンを記述します。基本的には、着信イベントを読み取る無限ループです。ステート マシンには、ラジオ モードと CD モードの 2 つの状態しかありません。イベントは、ラジオから CD へのモード変更、または次へ(ラジオの場合は次のプリセット、CD の場合は次のトラック) のいずれかです。

/********************************************************************/ 
#include <stdio.h> 

/************************************************************************/ 
typedef enum { ST_RADIO 、ST_CD }状態;  
        
        
 

typedef enum { EVT_MODE 、EVT_NEXT }イベント;  
        
        
 

イベントreadEventFromMessageQueue ( void ); 

/********************************************************************/ 
int main ( void ) { /* デフォルトの状態はラジオです */ STATES state = ST_RADIO ; int stationNumber = 0 ; int trackNumber = 0 ; 

    
     
     
     

  /* 無限ループ */ 
while ( 1 ) { /* 次の受信イベントを読み取ります。通常、これはブロッキング関数です。 */ EVENTS event = readEventFromMessageQueue ();   
  
    
       

    /* 状態とイベントを切り替えて、正しい遷移を実行します。 */ 
switch ( state ) { case ST_RADIO : switch ( event ) { case EVT_MODE : /* 状態を変更します */ state = ST_CD ; break ; case EVT_NEXT : /* ステーション番号を増やします */ stationNumber ++ ; break ; } break ;     
    
       
         
        
           
            
              
            
           
            
            
            
        
        

      case ST_CD : switch ( event ) { case EVT_MODE : /* 状態を変更する */ state = ST_RADIO ; break ; case EVT_NEXT : /* 次のトラックに進む */ trackNumber ++ ; break ; } break ; } } } 
         
        
           
            
              
            
           
            
            
            
        
        
    
  

Ginr は、半環代数用語で表現された有理パターン、関数、関係からマルチテープ有限状態オートマトンを生成する、産業用コンパイラです。以下の例は、上記の例と同等のバイナリ有理関数を示していますが、システムを初期状態に設定する遷移(nil、radio)が追加されています。ここで、入力シンボルnil、mode、next は、出力エフェクタcd、nextTrack、radio、nextStationを持つトランスデューサを駆動するイベントを表します。このような式は、通常、遷移を明示的にリストするよりもはるかに簡単に表現および維持できます。

ステートマシン = (
  （なし、ラジオ）
  （
    (モード、CD) (次、次のトラック)*
    (モード、ラジオ) (次、次のステーション)*
  )*
  （
    (モード、CD) (次、次のトラック)*
  ）？
);

コンパイルにより、イベントのシーケンスを CD/ラジオ デバイスの機能を作動させるエフェクタのシーケンスにマッピングする後続の (単一値の) バイナリ トランスデューサが生成されます。

ステートマシン:prsseq;

(START) なし [ ラジオ ] 1
1 モード [ CD ] 2
2 モード [ ラジオ ] 3
2 次へ [ 次のトラック ] 2
3モード[CD]2
3 次へ [ nextStation ] 3

この方法で離散システムをモデル化すると、構文 (イベントの許容可能な順序) とセマンティクス (エフェクターの実装) が明確に分離されます。イベントの構文上の順序とセマンティクス ドメインへの拡張は、代数的に操作できる記号 (半リング) ドメインで表現されますが、セマンティクスは、構文上の問題のない単純なエフェクター関数として手続き型プログラミング言語で表現されます。有理式は、システム ガバナンスに影響を与えるプロトコルの簡潔な全体マップを提供します。コンパイルされたオートマトンを後処理して、実行時の展開に効果的なコントローラーを取得します。

• 有限状態機械
• 仕様と記述言語

• Ginr (Ginr ホワイトペーパーとユーザーガイド)
• リボース（Ginr を使用して連続メディアを変換する方法を示します）

• ピートマン、ジョン B. (1977)。マイクロコンピュータベースの設計。ニューヨーク：McGraw-Hill、Inc. ISBN 0-07-049138-0。
• Brookshear, J. Glenn (1989)。計算理論: 形式言語、オートマトン、複雑性。カリフォルニア州レッドウッドシティ: Benjamin/Cummings Publish Company, Inc. ISBN 0-8053-0143-7。