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

手順1: 遷移を数える行列を作る。 状態を $s,t$ の順に並べ、$A_{q{q}^{\prime }}$ を「$q$ から $q^{\prime }$ へ移る記号の個数」とする。表より、$s$ からは $a$ で $s$、$b,c$ で $t$ へ移り、$t$ からは $a,b$ で $s$、$c$ で $t$ へ移る。よって
$$A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$$
である。長さ $n$ の文字列で $s$ から $t$ へ移るものの個数は $(A^n{)}_{st}$ に等しい。受理状態は $t$ だけなので、求める個数は $e_s^{\mathsf{T}}{A}^n{e}_t=(A^n{)}_{st}$（$(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$ のとき $2x+2y=0$ なので $\left(\begin{array}{c}1\\ -1\end{array}\right)$。
$$P=\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),P^{-1}=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right),D=\left(\begin{array}{cc}3& 0\\ 0& -1\end{array}\right)$$
とおくと $A=PD{P}^{-1}$ である。

手順4: $A^n$ を計算する。
$$A^n=P{D}^n{P}^{-1}=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\left(\begin{array}{cc}{3}^n& 0\\ 0& (-1{)}^n\end{array}\right)\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)=\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$ で、受理されるのは $b,c$ の 2 個。$n=2$ のとき $\frac{9-1}{2}=4$ で、受理されるのは $ab,ac,bc,cc$ の 4 個であり、一致する。

各状態から各状態への遷移の個数を並べた行列を $A$ とする（行が遷移前、列が遷移後の状態で、順序は $s,t$）。

$s$ からは、$a$ で $s$ へ 1 通り、$b,c$ で $t$ へ 2 通り進む。$t$ からは、$a,b$ で $s$ へ 2 通り、$c$ で $t$ へ 1 通り進む。したがって
$A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$。

長さ $n$ の文字列で $s$ から $t$ に至るものの個数は $(A^n{)}_{st}$、すなわち $A^n$ の (1,2) 成分である。

固有値は $\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)$ とおくと $P^{-1}=\frac{1}{2}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$ で、$A=P\mathrm{diag}(3,-1)P^{-1}$ となる。よって
$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)$。

(1,2) 成分より、受理される長さ $n$ の文字列の個数は $\frac{3^n-(-1{)}^n}{2}$。

検算：
- $n=1$ のとき、$(3+1)/2=2$。受理されるのは $b,c$ の 2 個で一致する。
- $n=2$ のとき、$(9-1)/2=4$。1 文字目で $s$ にいるのは $a$ の 1 通りで、そこから $t$ へは 2 通り。$t$ にいるのは 2 通りで、そこから $t$ へは $c$ の 1 通り。合計 $1\cdot 2+2\cdot 1=4$ で一致する。