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

遷移の数え上げ行列. 長さ $n$ の文字列を読んだ後に各状態にいる文字列の個数を $p_n,q_n,r_n$ とする（$p_0=1$, $q_0=r_0=0$）。表から、各状態へ入る遷移を数えると
- $p$ へ: $p\stackrel{a}{\to }p$, $q\stackrel{a}{\to }p$, $q\stackrel{b}{\to }p$
- $q$ へ: $p\stackrel{b}{\to }q$, $r\stackrel{a}{\to }q$
- $r$ へ: $p\stackrel{c}{\to }r$, $q\stackrel{c}{\to }r$, $r\stackrel{b}{\to }r$, $r\stackrel{c}{\to }r$

なので
$$p_{n+1}=p_n+2q_n,q_{n+1}=p_n+r_n,r_{n+1}=p_n+q_n+2r_n.$$
行列で書くと $(p_{n+1},q_{n+1},r_{n+1})=(p_n,q_n,r_n)T$、
$$T=\left(\begin{array}{ccc}1& 1& 1\\ 2& 0& 1\\ 0& 1& 2\end{array}\right)$$
（$T$ の $(i,j)$ 成分は状態 $i$ から状態 $j$ への遷移の本数）であり、$A_n=p_n$ である。

固有値. $T$ の固有多項式は
$$\det (\lambda E-T)={\lambda }^3-3{\lambda }^2-\lambda +3=(\lambda -3)(\lambda -1)(\lambda +1)$$
（トレース $3$、主小行列式の和 $(0-2)+(2-0)+(0-1)=-1$、行列式 $-3$ から）。固有値は $3,1,-1$ で相異なるので、$T$ は対角化可能であり、$p_n$ は
$$p_n=\alpha \cdot 3^n+\beta \cdot 1^n+\gamma \cdot (-1{)}^n$$
の形に書ける（ケーリー・ハミルトンの定理より $p_{n+3}=3p_{n+2}+p_{n+1}-3p_n$ をみたすことからもわかる）。

初期値. 漸化式から $(p_1,q_1,r_1)=(1,1,1)$、$(p_2,q_2,r_2)=(1+2,1+1,1+1+2)=(3,2,4)$。よって $p_0=1$, $p_1=1$, $p_2=3$ で
$$\alpha +\beta +\gamma =1,3\alpha +\beta -\gamma =1,9\alpha +\beta +\gamma =3.$$
第 3 式から第 1 式を引いて $8\alpha =2$、$\alpha =\frac{1}{4}$。すると $\beta +\gamma =\frac{3}{4}$, $\beta -\gamma =\frac{1}{4}$ より $\beta =\frac{1}{2}$, $\gamma =\frac{1}{4}$。したがって
$$A_n=p_n=\frac{3^n}{4}+\frac{1}{2}+\frac{(-1{)}^n}{4}=\frac{3^n+2+(-1{)}^n}{4}.$$

検算. $(p_3,q_3,r_3)=(3+4,3+4,3+2+8)=(7,7,13)$ で、式は $n=3$ のとき $\frac{27+2-1}{4}=7$。$(p_4,q_4,r_4)=(21,20,40)$ で、式は $\frac{81+2+1}{4}=21$。いずれも一致し、合計 $27=3^3$, $81=3^4$ も正しい。

答え: $A_n=\frac{3^n+2+(-1{)}^n}{4}$

長さ $n$ の文字列を読んだ後に状態 $p,q,r$ にいる文字列の個数をそれぞれ $x_n,y_n,z_n$ とする。$x_0=1,y_0=z_0=0$。

遷移表から、次の状態への入り方は
- $p$ へ: $p$ から $a$、$q$ から $a,b$ → $x_{n+1}=x_n+2y_n$
- $q$ へ: $p$ から $b$、$r$ から $a$ → $y_{n+1}=x_n+z_n$
- $r$ へ: $p$ から $c$、$q$ から $c$、$r$ から $b,c$ → $z_{n+1}=x_n+y_n+2z_n$

$A_n=x_n$（受理状態は $p$ のみ）。

係数行列 $T=\left(\begin{array}{ccc}1& 2& 0\\ 1& 0& 1\\ 1& 1& 2\end{array}\right)$ の特性多項式は
$\det (T-\lambda I)=(1-\lambda )({\lambda }^2-2\lambda -1)-2(1-\lambda )=(1-\lambda )(\lambda -3)(\lambda +1)$。
固有値は $1,3,-1$ なので $A_n=\alpha +\beta 3^n+\gamma (-1{)}^n$ と書ける。

$A_0=1,A_1=1,A_2=3$ を計算する（$n=1$: $(x,y,z)=(1,1,1)$、$n=2$: $(3,2,4)$）。
$\alpha +\beta +\gamma =1,\alpha +3\beta -\gamma =1,\alpha +9\beta +\gamma =3$。
1 式と 3 式の差から $8\beta =2$、$\beta =\frac{1}{4}$。1 式と 2 式の和から $2\alpha +4\beta =2$、$\alpha =\frac{1}{2}$。よって $\gamma =\frac{1}{4}$。

$A_n=\frac{2+3^n+(-1{)}^n}{4}$。

検算: 漸化式から $n=3$: $(7,7,13)$（合計 $27=3^3$）、$n=4$: $(21,20,40)$（合計 $81$）。公式では $A_3=(2+27-1)/4=7$、$A_4=(2+81+1)/4=21$ で一致する。