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

手順 1：遷移を数える行列を作る。 状態を $p,q$ の順に並べ、$A_{xy}$ を「状態 $x$ から状態 $y$ へ移る記号の個数」とする。表より、$p$ からは $3$ 個の記号すべてで $q$ へ移り、$q$ からは $0$ で $p$ へ、$1,2$ で $q$ へ移るので
$$A=\left(\begin{array}{cc}0& 3\\ 1& 2\end{array}\right).$$
$(A^n{)}_{xy}$ は $x$ から $y$ へ長さ $n$ の文字列で移る個数なので、初期状態 $p$・受理状態 $p$ より
$$a_n=e_p^{\mathsf{T}}{A}^n{e}_p=(A^n{)}_{pp}$$
である。

手順 2：固有値を求める。
$$\det (A-\lambda E)=\left|\begin{array}{cc}-\lambda & 3\\ 1& 2-\lambda \end{array}\right|={\lambda }^2-2\lambda -3=(\lambda -3)(\lambda +1)$$
より固有値は $\lambda =3,-1$。異なる 2 つの固有値をもつので対角化できる。

手順 3：固有ベクトルと $P$ を求める。
$\lambda =3$：$(A-3E)\mathbf{x}=0$ は $-3x_1+3x_2=0$ なので $\left(\begin{array}{c}1\\ 1\end{array}\right)$。
$\lambda =-1$：$(A+E)\mathbf{x}=0$ は $x_1+3x_2=0$ なので $\left(\begin{array}{c}3\\ -1\end{array}\right)$。
$$P=\left(\begin{array}{cc}1& 3\\ 1& -1\end{array}\right),\det P=-4,P^{-1}=\frac{1}{-4}\left(\begin{array}{cc}-1& -3\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}\frac{1}{4}& \frac{3}{4}\\ \frac{1}{4}& -\frac{1}{4}\end{array}\right)$$
とおくと $A=PD{P}^{-1}$、$D=\left(\begin{array}{cc}3& 0\\ 0& -1\end{array}\right)$。

手順 4：$A^n$ の $(p,p)$ 成分を計算する。 $A^n=P{D}^n{P}^{-1}$ で、
$$P{D}^n=\left(\begin{array}{cc}{3}^n& 3(-1{)}^n\\ 3^n& -(-1{)}^n\end{array}\right).$$
この第 1 行と $P^{-1}$ の第 1 列 $\left(\begin{array}{c}\frac{1}{4}\\ \frac{1}{4}\end{array}\right)$ の積をとって
$$a_n=(A^n{)}_{pp}=\frac{3^n}{4}+\frac{3(-1{)}^n}{4}=\frac{3^n+3\cdot (-1{)}^n}{4}.$$

確認： $n=0$ で $\frac{1+3}{4}=1$（空文字列のみ）、$n=1$ で $0$（$p$ からは必ず $q$ へ移る）、$n=2$ で $\frac{9+3}{4}=3$（$p\to q\to p$ は $3\times 1=3$ 通り）、$n=3$ で $\frac{27-3}{4}=6$（$p\to q\to q\to p$ は $3\times 2\times 1=6$ 通り）となり、直接数えた結果と一致する。

よって $a_n=\frac{3^n+3\cdot (-1{)}^n}{4}$。

$M$ の遷移を数える行列を $A$ とする。$A_{ij}$ は状態 $i$ から状態 $j$ への遷移を起こす入力記号の個数で、状態の順は $(p,q)$ とする。

$p\to q$ は記号 $0,1,2$ の 3 通り、$p\to p$ は 0 通りである。$q\to p$ は記号 $0$ の 1 通り、$q\to q$ は記号 $1,2$ の 2 通りである。よって
$A=\left(\begin{array}{cc}0& 3\\ 1& 2\end{array}\right)$。

初期状態 $p$ から長さ $n$ の文字列を読んで状態 $p$ にいる文字列の個数は $(A^n{)}_{pp}$ である。受理状態は $p$ のみなので、$a_n=(A^n{)}_{pp}$ となる。

固有多項式は ${\lambda }^2-2\lambda -3=(\lambda -3)(\lambda +1)$ なので、固有値は $3,-1$ である。
$A$ は異なる 2 つの固有値をもつので対角化可能であり、$(A^n{)}_{pp}=\alpha 3^n+\beta (-1{)}^n$ と書ける。

$n=0$ で $A^0=E$ より $a_0=1$ だから $\alpha +\beta =1$。
$n=1$ で $a_1=A_{pp}=0$ だから $3\alpha -\beta =0$。
これを解くと $\alpha =1/4,\beta =3/4$ となる。

よって $a_n=\frac{3^n+3(-1{)}^n}{4}$。

検算：$n=2$ のとき、受理されるのは $p\to q\to p$ の経路で、$3\cdot 1=3$ 個。公式は $(9+3)/4=3$ で一致する。
$n=3$ のとき、受理されるのは $p\to q\to q\to p$ の経路のみで、$3\cdot 2\cdot 1=6$ 個。公式は $(27-3)/4=6$ で一致する。