オートマトン・形式言語の問題

手順 1：遷移を数える行列を作る。
状態の順を $s,t$ とし、$A_{q{q}^{\prime }}$ を「状態 $q$ から状態 $q^{\prime }$ へ移る記号の個数」とする。
- $s$ から：$0$ で $s$（1 個）、$1,2$ で $t$（2 個）
- $t$ から：$0,1$ で $s$（2 個）、$2$ で $t$（1 個）

よって
$$A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$$
である。$A^n$ の $(q,q^{\prime })$ 成分は、$q$ から出発して長さ $n$ の文字列で $q^{\prime }$ に到達する文字列の個数になる。初期状態は $s$、受理状態は $t$ なので、求める個数は $A^n$ の $(s,t)$ 成分、すなわち $(1,2)$ 成分である。

手順 2：固有値を求める。
$$\det (A-\lambda E)=(1-\lambda {)}^2-4=(\lambda -3)(\lambda +1)$$
より、固有値は $\lambda =3,-1$ である。

手順 3：固有ベクトルを求めて対角化する。
$\lambda =3$：$(A-3E)\mathbf{x}=0$ は $-2x+2y=0$ なので、固有ベクトルとして $\left(\begin{array}{c}1\\ 1\end{array}\right)$ がとれる。
$\lambda =-1$：$(A+E)\mathbf{x}=0$ は $2x+2y=0$ なので、固有ベクトルとして $\left(\begin{array}{c}1\\ -1\end{array}\right)$ がとれる。

$P=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ とおくと、$\det P=-2\ne 0$ であり、
$$P^{-1}=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),P^{-1}AP=\left(\begin{array}{cc}3& 0\\ 0& -1\end{array}\right)$$
となる。

手順 4：$A^n$ を計算する。
$$A^n=P\left(\begin{array}{cc}{3}^n& 0\\ 0& (-1{)}^n\end{array}\right)P^{-1}=\frac{1}{2}\left(\begin{array}{cc}{3}^n+(-1{)}^n& 3^n-(-1{)}^n\\ 3^n-(-1{)}^n& 3^n+(-1{)}^n\end{array}\right)$$

手順 5：必要な成分を取り出す。
求める個数は $(1,2)$ 成分なので
$$\frac{3^n-(-1{)}^n}{2}$$
である。

確認： $n=1$ のとき $\frac{3+1}{2}=2$ で、受理されるのは「1」「2」の 2 個であり一致する。$n=2$ のとき $\frac{9-1}{2}=4$ である。漸化式で数えると、長さ 1 で $s$ に 1 個、$t$ に 2 個あり、長さ 2 で $t$ に到達する個数は $1\cdot 2+2\cdot 1=4$ となり、これも一致する。

遷移を数える行列を $A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$ とする。ここで $A_{ij}$ は状態 $i$ から状態 $j$ へ移る入力文字の個数で、行・列の順は $(s,t)$ とする。たとえば $s\to s$ は文字 0 の 1 通り、$s\to t$ は文字 1,2 の 2 通り、$t\to s$ は文字 0,1 の 2 通り、$t\to t$ は文字 2 の 1 通りである。

長さ $n$ の文字列で、$s$ から始めて $t$ で終わるものの個数は $(A^n{)}_{st}$ に等しい。

固有値は $\det (A-\lambda I)=(1-\lambda {)}^2-4=0$ より $\lambda =3,-1$ である。固有ベクトルは、$\lambda =3$ で $(1,1{)}^T$、$\lambda =-1$ で $(1,-1{)}^T$ となる。

$P=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ とおくと、$A=P\mathrm{diag}(3,-1)P^{-1}$ で、$P^{-1}=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ である。したがって
$A^n=\frac{1}{2}\left(\begin{array}{cc}{3}^n+(-1{)}^n& 3^n-(-1{)}^n\\ 3^n-(-1{)}^n& 3^n+(-1{)}^n\end{array}\right)$

よって $(A^n{)}_{st}=\frac{3^n-(-1{)}^n}{2}$ である。

検算: $n=1$ のとき $(3+1)/2=2$ で、受理される文字列は 1,2 の 2 個であり一致する。$n=2$ のとき $(9-1)/2=4$ である。実際、$s\to s\to t$ が 1×2=2 通り、$s\to t\to t$ が 2×1=2 通りで、合計 4 であり一致する。