制御フローグラフと実行

制御フローグラフによるプログラム $p$ とは、次のものの組をいう。

• 有向グラフ $G = (N, E)$（定義 2.1［グラフアルゴリズム］）と、入口 $s \in N$、出口 $t \in N$。$t$ の出次数は $0$。
• 状態の集合 $\Sigma$、入力から初期状態への写像 $\mathrm{in} : X \to \Sigma$、状態から出力への写像 $\mathrm{out} : \Sigma \to Y$。
• $t$ 以外の各頂点 $n$ は文か判定のどちらかである。文 $n$ は出次数が $1$ で、写像 $a_n : \Sigma \to \Sigma$（文の効果）をもつ。判定 $n$ は出次数が $2$ で、2 本の辺に $1$（真）と $0$（偽）のラベルが付き、写像 $d_n : \Sigma \to \{0, 1\}$ をもつ。$d_n$ は、条件 $c_{n,1}, \ldots, c_{n,k} : \Sigma \to \{0, 1\}$ とブール関数 $\varphi_n : \{0, 1\}^k \to \{0, 1\}$（定義 2.1［コンピュータアーキテクチャとCPUの構造］）によって $d_n(\sigma) = \varphi_n(c_{n,1}(\sigma), \ldots, c_{n,k}(\sigma))$ と表されているとする。

入力 $x$ に対する実行とは、次で定まる列 $(n_0, \sigma_0), (n_1, \sigma_1), \ldots$ をいう。$n_0 = s$、$\sigma_0 = \mathrm{in}(x)$。$n_i$ が文なら $\sigma_{i+1} = a_{n_i}(\sigma_i)$ で、$n_{i+1}$ は $n_i$ から出る辺の先。$n_i$ が判定なら $\sigma_{i+1} = \sigma_i$ で、$n_{i+1}$ はラベル $d_{n_i}(\sigma_i)$ の辺の先。$n_L = t$ となったら実行は終わり、$p(x) = \mathrm{out}(\sigma_L)$ を出力とする。このとき頂点の列 $\pi_p(x) = (n_0, \ldots, n_L)$ は $s$ から $t$ への歩道（定義 2.2［グラフアルゴリズム］）で、これを $x$ の実行経路という。$t$ に至らないとき $p(x)$ は定まらない。

頂点・辺・$s$ から $t$ への歩道が、ある $x \in D$ の実行経路に現れる（歩道の場合は実行経路に等しい）とき、それは実行可能であるという。