1. 序章

このチュートリアルでは、ステートマシンとそのアプリケーションの基本を学習します。

このチュートリアルの終わりに、有限状態マシンに関連する概念に精通し、それらの表現を描くことができるようになります。

2. ステートマシン

有限状態マシンは、オートマトン理論における分析の基本的な概念単位の1つです。 これらは当初、動作が離散パラメーターの有限集合に依存するシステムの動作を形式化するために開発されました。

システムの動作が十分に小さいパラメーターのセットに従って明確に定義されている場合、通常、有限状態マシンを使用します。 具体的なアプリケーションでは、システムが機能するルールの明示的な定義も必要ですが、常に存在するとは限りません。

ステートマシンのパラメータが特定の瞬間に想定する特定の構成は、「状態」と呼ばれます。

これらのパラメーターの可能な値は有限であると想定しているため、その場合、そのマシンの可能な状態の数も有限になります。 たとえば、各パラメーターが2つの binary 値のいずれかを想定できる場合、異なる可能性のある状態の総数が得られます。

たとえば、次の場合：

3. 移行ルール

ステートマシンの状態をとして示すことができます。ここで、はその状態が観測された離散時間を示します。

ステートマシンの構成を経時的に観察すると、その構成の変更方法がおそらくいくつかの規則性を示していることに気付くことができます。 限界の場合、状態がまったく変化しないステートマシンを観察できます。

ただし、重要な状態マシンは、私たちにとってより興味深い方法で状態を変更する傾向があります。

これは、たとえば、1つおきの間隔で2つの状態を交互に繰り返します。

これらの規則性を完全に理解している場合は、それらを特定の構成を新しい構成に関連付ける一連のルールとしてモデル化できます。これにより、マシンの状態が更新されます。

このため、ステートマシンは、そのパラメーターだけでなく、その状態がどのように変化するかを決定する一連のルールも含みます。

4. 表現

有限状態マシンは、さらにグループに細分化できます。 最も重要な違いは、それらを孤立したシステムと見なすかどうかです。

それらを孤立したシステムと見なす場合、新しい状態を決定するルールは、現在の状態のみを考慮に入れることができます。 単純な更新ルールは次のようになります。

このタイプのオートマトンはムーアマシンの名前を取り、環境を感知する必要はありません。 ただし、マシンが分離されたシステムでない場合は、外部環境から発信された入力を持つことができます。

この場合、オートマトンの将来の状態は、現在の状態と受信した入力によって同時に決定されます。 このタイプのオートマトンはMeelyマシンの名前を取り、その典型的な例はサーモスタットです。 サーモスタットの場合、外部センサーによって読み取られた温度により、マシンの状態が変化します。

5. アプリケーション

有限状態マシンをその名前で呼ぶことはあまりありませんが、私たちはすでに有限状態マシンに精通しています。 パソコン、スマートフォン、電卓はすべて、有限数の状態の1つを想定できるマシンの例です。 このため、それらを有限状態マシンとして研究し、オートマトン理論を適用してそれらの動作をモデル化することができます。

有限状態マシンのアプリケーションのもう1つの一般的なケースは、グラフィカルモデルのアニメーションです。 たとえば、立っている状態から歩いている状態、そして走っている状態に移行するビデオゲームのキャラクターは、Meelyマシンとしてモデル化できます。

他のチュートリアルでは、正規表現を使用して文字列を解析する方法についても説明しました。 正規表現がコンパイルされるたびに、が有限状態マシンに変換されます。 このオートマトンは、初期状態を構成する一連の状態であるアルファベットを考慮し、その後、一連の許容可能な状態に対してその最終状態を評価します。

6. 結論

この記事では、有限状態マシンのコンポーネント、表現、およびアプリケーションについて学習しました。