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

長さ $n$ の文字列 $w$ のうち、$s_0$ から読み始めて読み終えたときの状態が $s_0,s_1,s_2$ になるものの個数を、それぞれ $x_n,y_n,z_n$ とする。$x_0=1,y_0=z_0=0$ であり、どの文字列も 3 つの状態のどれか 1 つで終わるので
$$x_n+y_n+z_n=3^n(n\ge 0)$$
が成り立つ。求めるものは $y_n$ である。

漸化式. 長さ $n+1$ の文字列を「長さ $n$ の部分 ＋ 最後の 1 文字」に分け、最後の 1 文字でどの状態に移るかを表から読むと:
- $s_2$ へ入る遷移は、どの状態からも文字 $2$ による 1 通りずつ。よって $z_{n+1}=x_n+y_n+z_n=3^n$。
- $s_1$ へ入る遷移は、$s_0$ から文字 $0,1$ の 2 通り、$s_1$ から文字 $0$ の 1 通り。よって $y_{n+1}=2x_n+y_n$。

$y_n$ の計算. $z_n=3^{n-1}(n\ge 1)$ なので、$n\ge 1$ のとき
$$x_n=3^n-y_n-z_n=3^n-3^{n-1}-y_n=2\cdot 3^{n-1}-y_n.$$
これを $y_{n+1}=2x_n+y_n$ に代入して
$$y_{n+1}=4\cdot 3^{n-1}-y_n(n\ge 1).$$
また $y_1=2x_0+y_0=2$（文字列 $0$ と $1$）。

特殊解として $y_n=a\cdot 3^{n-1}$ を代入すると $3a=4-a$ より $a=1$。同次式 $y_{n+1}=-y_n$ の一般解は $c(-1{)}^n$ なので、$y_n=3^{n-1}+c(-1{)}^n$ とおける。$y_1=1-c=2$ から $c=-1$。よって
$$y_n=3^{n-1}-(-1{)}^n(n\ge 1).$$

確認. $n=1$: $1+1=2$（$0,1$）。$n=2$: $3-1=2$。実際、長さ 2 で $s_1$ に終わるのは、1 文字目で $s_1$ に入り 2 文字目が $0$ のもの（$00,10$）だけで、1 文字目が $2$ のときは $s_2$ から 1 文字で $s_1$ に入れない。$n=3$: $9+1=10$ で、$y_3=2x_2+y_2=2\cdot 4+2=10$（$x_2=9-2-3=4$）と一致する。

したがって求める個数は $3^{n-1}-(-1{)}^n$ である。

長さ $n$ の文字列で $s_0$ から出発して状態 $s_0,s_1,s_2$ に至るものの個数をそれぞれ $x_n,y_n,z_n$ とする（$x_0=1,y_0=z_0=0$）。表を状態ごとに「入る遷移」で整理すると
- $s_0$ へ入る: $s_1\stackrel{1}{\to }{s}_0$（1 通り）、$s_2\stackrel{0,1}{\to }{s}_0$（2 通り）
- $s_1$ へ入る: $s_0\stackrel{0,1}{\to }{s}_1$（2 通り）、$s_1\stackrel{0}{\to }{s}_1$（1 通り）
- $s_2$ へ入る: 各状態から文字 $2$（3 通り）

よって
$$x_{n+1}=y_n+2z_n,y_{n+1}=2x_n+y_n,z_{n+1}=x_n+y_n+z_n=3^n.$$

$z_n=3^{n-1}$（$n\ge 1$）。したがって $n\ge 1$ で $x_n+y_n=3^n-3^{n-1}=2\cdot 3^{n-1}$。これを $y_{n+1}=2(x_n+y_n)-y_n$ に入れると、$n\ge 1$ で
$$y_{n+1}=4\cdot 3^{n-1}-y_n,y_1=2.$$
特殊解を $c\cdot 3^n$ とおくと $3c=\frac{4}{3}-c$ より $c=\frac{1}{3}$。一般解は $y_n=3^{n-1}+A(-1{)}^n$。$y_1=2$ より $1-A=2$、$A=-1$。
$$y_n=3^{n-1}-(-1{)}^n.$$

受理状態は $s_1$ のみなので、答えは $y_n=3^{n-1}-(-1{)}^n$。

検算: 直接計算で $(x_n,y_n,z_n)$ は $n=1:(0,2,1)$, $n=2:(4,2,3)$, $n=3:(8,10,9)$, $n=4:(28,26,27)$。各行の和は $3^n$。式は $n=1:1+1=2$, $n=2:3-1=2$, $n=3:9+1=10$, $n=4:27-1=26$ で一致する。