状態機械
状態機械は現在の状態を一つ覚え、イベントを読み、遷移規則から次の状態と動作を選びます。キーは (state, event) です。イベントだけでは決まらず、同じ push が拒否にも通過にもなります。
改札を例にします。規則は「押されたら何かする」ではなく、「施錠中に押されたら拒否」「解錠後に押されたら通す」です。イベントと記憶している状態が結果を決めます。
状態機械の仕組み
本レッスンの決定性有限状態機械は四つの部分を持ちます。
- 有限の状態集合：
lockedとunlocked。 - 有限の入力イベント集合：
coinとpush。 (state, event)をキーにする遷移表。- 初期状態：
locked。
イベントを読むたびに現在の状態と組み合わせ、表を引きます。該当行は next_state と出力する action を示します。state = next_state を実行してから、次のイベントへ進みます。
グラフの辺は event / action と表記します。coin / unlock なら、イベントは coin、出力する動作は unlock です。グラフは関係を示し、表は実行動作を正確に定義します。食い違う場合は遷移表が基準です。
自己ループも遷移です。locked + push は施錠を保ち、reject を出します。unlocked + coin は解錠を保ち、thank を出します。状態が変わらなくても、イベントを処理して動作を出力しています。
ステップごとの解説
既定のイベント列は push, coin, push, coin, coin, push、初期状態は locked です。
- 開始。 二つの状態それぞれに二つのイベントがあり、表には四つの有効な規則があります。
pushを読む。(locked, push)は次の状態をlocked、動作をrejectとします。押す動作を拒否し、自己ループで施錠を保ちます。coinを読む。(locked, coin)はunlockedとunlockを選び、解錠します。- 再び
push。 ステップ 2 と同じイベントでも、キーは(unlocked, push)です。passを出力し、lockedへ戻ります。 coinを読む。(locked, coin)により再び解錠します。- もう一度
coin。(unlocked, coin)はunlockedを保ち、thankを出します。追加の硬貨で施錠するのではなく、別の自己ループを通ります。 - 最後の
push。(unlocked, push)が人を通し、lockedに戻します。
記録には、push と coin それぞれ二通りの意味が現れます。イベントの発生時の状態が異なるためです。挙動を決めるのは (state, event) です。
次に missing-rule へ切り替えます。最初の有効な coin で locked から unlocked へ移り、その後で timeout を読みます。表に (unlocked, timeout) がないため、その位置で停止します。規則を勝手に補いません。
現在の状態が重要な理由
イベントだけで表を引くと、push の意味が曖昧になります。施錠中なら reject、解錠中なら pass が正解です。状態を捨てると選べません。
多くのシステムがこの記憶を使います。TCP の端点は LISTEN、SYN-SENT、ESTABLISHED でセグメントの扱いを変えます。パーサーも数字の中、文字列の中、区切り文字の後で同じ文字を異なる意味に取ります。UI のボタンも idle、loading、disabled によってクリックへの反応が変わります。
大きなシステムでは状態、イベント、ガード条件、付随データを増やしますが、現在の状態と入力から次を決める構造は残ります。
境界ケース
- 空のイベント列。 初期状態
lockedのままで、表を引きません。 - 同じ状態でイベントを繰り返す。 施錠中の
push, pushは二回ともrejectを出し、施錠を保ちます。 - 別の状態で同じイベント。 投入前後の
pushは、状態によってキーが変わります。 - 未知のイベント。 表に
timeoutの規則がないので、遷移の欠落位置で止まります。 - 自己ループ。 次の状態が同じでも、イベントを消費し、動作を出力します。
よくある間違い
- イベントだけを入力と考える。 遷移関数の入力は
(state, event)で、eventだけではありません。 - 自己ループを無操作と考える。 拒否、感謝、ログ記録、再試行、警報などの動作を伴えます。
- 表を定義せずにグラフだけ描く。 グラフは読みやすく、表は挙動を正確にします。
- 既定の規則を明記しない。 欠けた行をすべて「その場にとどまる」と扱うなら、それも規則として書きます。
- 初期状態を忘れる。 同じイベント列でも、開始状態が変われば軌跡が変わることがあります。
このレッスンでの簡略化
一度に一つの現在状態と一つのイベントを扱い、各有効な遷移に表の一行を対応させます。実際のシステムにはタイマー、並行する主体、ガード条件、再試行、遷移に伴うデータもあります。これらも、イベントの意味を決める前に現在の状態を知るという前提に立ちます。