Finite State Machines

最近の JavaScript 界では Finite State Machines がよく話題になっています。

GitHub で 11,000 以上のスターが付いている XState という人気のライブラリがありますが、最近このライブラリに遭遇し、Twitter などでこのプロジェクトについて読み続けています。

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

このデジタルデザインのコースでは、情報の符号化、ブール代数、組み合わせネットワーク、逐次回路、逐次状態機械、演算回路、VHDLなどについて学びました。

フロントエンドエンジニアリングに適用された有限ステートマシンのトピックはとても驚きました。私は物事を単純化するのが好きなので、試験に合格するための理論的なものではなく、普通の人間のためのちょっとした説明を書くことにしました。

ステートマシン

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

世の中はステートマシンであふれていて、いたるところで目にすることができますが、おそらくそのようには考えていなかったでしょう。

最も一般的でよく見られる例は交通信号です。

どの時点でも、交通信号は定義された状態を持っています。典型的には、次のいずれかです。

緑のランプが点灯していて、他の2つのランプが消灯している
赤のランプが点灯していて、他の2つのランプが消灯している
黄色のランプが点灯していて、他の2つのランプが消灯している
。

(一部のセマフォは若干異なりますが、この例のためには気にしません)

ステートマシンの用語では、ライトが点灯または消灯することを出力と呼びます。

この3つのシナリオのそれぞれを状態と呼びます。交通セマフォは、入力を受け取ると状態を変化させます。通常は、信号機が緑、黄、赤であるべき時間を決定する固定タイマーだけです。

ステートマシンでは、入力に応答してのみ状態が変化します (そして私たちは遷移を持ちます)。

有限のステートマシン

私たちの信号機のステートマシンは、有限の数の状態を持っているので、有限と言われています。

システムによっては、無限の数の状態を持っているかもしれません。

しかし、信号機はどうでしょう。

でも、交通信号は簡単で、上で述べたように3つの状態があります。

有限状態機械の例は、もっとたくさんあります。

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

しかし、非常に単純で簡単に推論できる交通信号機の例にこだわりましょう。

ステートマシンのモデル化

もちろん、交通信号機は単独では存在しません。それはもうひとつの有限状態機械であり、交差点の各道路の各側に設置された各交通信号機に対して、複数の異なる有限状態機械が含まれており、それらは同期して動作します。

今は考えないでください。

私たちには初期状態があります。

緑の状態が50秒続くと、セマフォをyellowyellowred状態に移行し、32秒間そこに留まります。これは、その道路が二次的なものであり、緑の時間が短くて済むからです。この後、セマフォは緑の状態に戻り、電気が停止してセマフォがリセットされるまで、このサイクルは無限に続きます。

このようにモデル化することができます。

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

状態	入力	次の状態	出力
Green	Timer 50s	Yellow	Green light on,
Yellow	Timer 8s	Red	Yellow light on,
Red	Timer 32s	Green	Red light on, other off

私たちの単純なケースでは。

私たちの単純なケースでは、マシンのどの状態が与えられても、行くべき 1 つの論理的な状態があるだけですので、私が作成した表とグラフは非常に単純です。

しかし、システムがより複雑になり始めると、このような図や分析を用意しておくことは非常に役に立ちます。

A Finite State Machine with more complex State Transitions

上記の例は非常にシンプルです。

私たちの現実世界のシナリオは次のようなものです: 1 つのドア、2 つのボタン、3 つの照明がある家があります。

家に入ると、p1p2という2つの押しボタンのうちの1つを押すことができます。

これが玄関の照明で、上着を脱ぐことができるとイメージしてください。

ボタンp1l1l2p2l1l3がオンになります。

さらに、p1p2の2つのボタンのいずれかを押すと、現在点灯しているライトが消灯し、システムの初期状態に戻ります。

この有限状態機械は、最初のものより少し複雑です。なぜなら、今回は入力に応じて複数のルートを持つことができるからです。

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

明かりがついていない
l1 明かりがついている
l2 明かりがついている。 turned on
l3 turned on

2つの入力があります。

p1
p2

初期状態からスタートして、時間の経過とともに入力がどのようにトリガーされるかによって起こりうることをすべてモデル化しようとすると、次のようになります。

これを表にまとめてみました。

となります。

状態	入力	次の状態
ライトが点灯しない	`p1`押された	`l1`点灯した
ライトが点灯しない	`p2`が押された	`l1`がオンになった
`l1`がオンになった	`p1`が押された	`l1`がオンになった。押されている	`l2` オンになっている
`l1` オンになっている	`p2` 押されている	`l3` ON
`l2` ON	`p1` Press	点灯しません。
`l2` ON	`p2` pressed	no lights turned on
`l3` オンになった	`p1` 押された	オンになったライトがない
`l3` オンになった	`p2` 押された	ライトが点灯しない

それは短くてシンプルな説明です。でも、これで「カチッ」とくるかもしれませんね。

Heading