有限状態機械

ステートマシンとは何かの簡単な概要と簡単な例

についての話がたくさんあります有限状態機械最近のJavaScriptの土地。

と呼ばれるこの人気のあるライブラリがありますXState、最近出くわしたGitHubに11000を超える星があり、Twitterやその他の場所でそれについて読み続けています。とてもクールなプロジェクトです。

私は20年前、高校で有限状態機械とオートマトンに初めて会いました。その後、大学のデジタルデザインコースで再び会いました。

このデジタルデザインコースは、情報のエンコード、ブール代数、組み合わせネットワーク、シーケンシャル回路、シーケンシャルステートマシン、算術回路、VHDLなどに関するものでした。

フロントエンドエンジニアリングに適用された有限状態機械のトピックは非常に素晴らしいと思いました。古い本に戻って、それらの適切な説明を見つけることができるかどうかを確認しました。

私はたくさんの情報を見つけました、そしてもちろん教科書であるために物事は必要以上に複雑になります(IMHO)。私は物事を単純化するのが好きで、理論的なものや試験に合格するために作られたものではなく、普通の人間のために少し説明を書くことにしました。現実の世界に適用できるもの。

ステートマシン

有限ステートマシンとは何かを調べる前に、まずステートマシンとは何かを紹介したいと思います。

世界はステートマシンでいっぱいです。あなたはどこでもそれらを見ることができます、しかし多分あなたはそれらをそのように考えていませんでした。このチュートリアルを読んだ後、あなたはあなたの友人に言っている現実世界のオブジェクトを指摘するでしょう。ステートマシン」(友達のオタクレベルによって異なります)。

最も人気があり、一般的に見られる例は信号機

いつでも、トラフィックセマフォには定義された状態があります。通常、次のいずれかです。

  • 緑色のライトが点灯し、他の2つのライトが消灯しています
  • 赤いライトがオンになっていて、他の2つのライトがオフになっています
  • 黄色のライトが点灯し、他の2つのライトが消灯します

Traffic lights

(一部のセマフォはわずかに異なりますが、この例では気にしません)

ステートマシンの用語では、ライトがオンまたはオフになっていることを「出力

これらの3つのシナリオはそれぞれと呼ばれます状態。交通セマフォは、入力を受信すると状態を変更します。通常は、信号が緑、黄、赤になる時間を決定する固定タイマーです。

この場合のタイマーは入力システムの。一部のセマフォには、歩行者が押すと赤が車に表示されるボタンがあり、それは別の入力になります。

ステートマシンでは、状態は変更することしかできません(そして、遷移)入力に応じて。

有限状態機械

私たちの信号機のステートマシンは有限の状態の数には限りがあるからです。

一部のシステムには、無限の数の状態がある場合があります。

世界の生態系モデル、または昆虫の生活のように。有限数の状態でそれを定義することはできません。

しかし、信号機?これは簡単なことで、前述のように3つの状態があります。

使用できる有限状態マシンの例は他にもたくさんあります。

  • 自動販売機
  • 地下鉄の入り口の改札口
  • 暖房システム
  • 自動化された地下鉄システム
  • 自動運転車システム
  • エレベーター

しかし、信号機の例に固執しましょう。これは非常に単純で、簡単に推論できます。

ステートマシンのモデリング

もちろん、信号機は孤立して存在しません。これは別の有限状態マシンであり、交差点の各道路の両側に設置された信号機デバイスごとに複数の異なる有限状態マシンが含まれており、同期して動作します。

Crossroads

今は考えないでください。 1つの単一のトラフィックセマフォに焦点を当てましょう。

上で述べたように、緑、赤、黄色と呼ぶことができる3つの状態があります。

The 3 states

初期状態があります。信号機をリセットすると、信号機がgreen状態。

Initial state

緑の状態が50秒経過した後、セマフォをに移動するタイマーがあります。yellow状態。 8秒ありますyellow状態、それから私達はに移動しますredその道路は二次的であり、緑の時間が少ないに値するので、私たちはそこに32秒間座っています。この後、セマフォは緑色の状態に戻り、電力が停止してセマフォが再び電力を得るとリセットされるまで、サイクルが無期限に続きます。

合計で、90秒のサイクルがあります。

これが私たちがそれをモデル化する方法です:

The model

でモデル化することもできます状態遷移表、を示しています状態マシンは現在入っています、何ですか入力それが受け取る、何ですか次の状態、 そしてその出力

状態 入力 次の状態 出力
タイマー50秒 緑色のライトがオン、その他はオフ
タイマー8秒 黄色のライトがオン、その他はオフ
タイマー32秒 赤信号がオン、その他がオフ

私たちの単純なケースでは、マシンのどの状態でも、移動する論理状態が1つしかないため、作成した表とグラフは非常に単純です。

しかし、システムがより複雑になり始めたときは、単にすべてを頭の中に置いておくよりもはるかに簡単にアプリケーションについて推論できるため、そのような図と分析を用意しておくと非常に役立ちます。

より複雑な状態遷移を持つ有限状態マシン

上記の例は非常に単純です。ここで、別の有限状態マシンをモデル化してみましょう。

私たちの現実のシナリオはこれです:私たちは1つのドア、2つのボタンと3つのライトを備えた家を持っています。

デフォルトの状態では、ライトはすべてオフになっています。

lights

あなたが家に入るとき、あなたはあなたが持っている2つの押しボタンの1つを押すことができます、p1またはp2。これらのボタンのいずれかを押すと、l1ライトが点灯します。

これが入り口のライトだと想像してみてください。ジャケットを脱ぐことができます。終わったら、どの部屋に行きたいかを決めます(たとえば、キッチンや寝室)。

ボタンを押すとp1l1オフにしてl2オンになります。代わりにボタンを押すとp2l1オフにしてl3オンになります。

2つのボタンのいずれかをもう一度押すと、p1またはp2、現在点灯しているライトが消灯し、システムの初期状態に戻ります。

今回は入力に応じて複数のルートを持つことができるため、この有限状態マシンは最初のマシンよりも少し複雑です。

これをモデル化しましょう。

基本的に4つの状態があります。

  • ライトが点灯していません
  • l1オン
  • l2オン
  • l3オン

model lights

2つの入力があります:

  • p1
  • p2

初期状態から始めて、入力が時間の経過とともにどのようにトリガーされるかに応じて発生する可能性のあるすべてをモデル化しようとすると、次のようになります。

State transitions

この表を使用して要約できます。

状態 入力 次の状態
ライトが点灯していません p1押された l1オン
ライトが点灯していません p2押された l1オン
l1オン p1押された l2オン
l1オン p2押された l3オン
l2オン p1押された ライトが点灯していません
l2オン p2押された ライトが点灯していません
l3オン p1押された ライトが点灯していません
l3オン p2押された ライトが点灯していません

これは短くて簡単な説明ですが、「クリック」する可能性があります。


その他のコンピューターチュートリアル: