6.1 状態と遷移

状態機械 (state machine) は形式的には何らかの集合上の二項関係に少量の情報を付けたものに過ぎない。この集合を状態集合 (state set)、状態集合の要素を状態 (state)、二項関係を遷移関係 (transition relation)、遷移関係を表す図に含まれる矢印 ── グラフの要素 ── を遷移 (transition) と呼ぶ。本書では状態 \(q\) から状態 \(r\) への遷移を \(q \to r\) と表記する。遷移関係は状態機械の状態グラフ (state graph) とも呼ばれる。二項関係に加えて初期状態 (start state) と呼ばれる特別な状態を指定すると、状態機械の定義となる。

簡単な例として上限のあるカウンターを考えよう。このカウンターは \(0\) から \(99\) までの整数を数えることができ、\(100\) 以降はオーバーフローする。この仕組みをモデル化した状態機械を図 \(\text{6.1}\) に示す。この図では円が状態、矢印が遷移、二重の円が初期状態 \(0\) をそれぞれ表す。

99 までの整数を数えられるカウンター — 図 6.1\(99\) までの整数を数えられるカウンター

カウンターを表す状態機械 (図 \(\text{6.1}\)) を数学の言葉で正確に表現すると次のようになる:

\[ \begin{aligned} \text{状態} &::= \left\{ 0,\ 1,\ \ldots,\ 99,\ \text{overflow} \right\} \\ \text{遷移} &::= \left\{ n \to n+1 \; | \; 0 \leq n < 99 \right\} \\ & \quad\ \ \ \cup\ \left\{ 99 \to \text{overflow},\ \text{overflow} \to \text{overflow} \right\} \\ \text{初期状態} &::= 0 \end{aligned} \]

この状態機械は一度 \(\text{overflow}\) 状態に達すると以降は \(\text{overflow}\) 状態に留まり続けるので、あまり役に立たない。

デジタル回路や文字列マッチングアルゴリズムをモデル化する状態機械の多くは有限個の状態しか持たないのに対して、停止しない計算処理をモデル化する状態機械は無限に多くの状態を持つ場合がある。例えば、\(99\) までしか数えられないカウンターではなく、オーバーフローしない「青天井」カウンターを考えてみてほしい。この青天井カウンターは非負整数全体からなる無限の状態を持つので、図で表現するのは骨が折れる。

状態機械の状態や遷移にラベルが付けられる場合もある。そういったラベルは入力、出力、コスト、容量、確率といった様々な値を表す。本書ではそういった状態機械を扱わないので、状態機械の定義にラベルは含まれない。図 \(\text{6.1}\) のように状態に名前を付けることはあるものの、この名前は状態機械の定義に含まれない。