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

長さ $n$ の文字列を読み終えたとき状態 $p,q,r$ にいる文字列の個数を、それぞれ $x_n,y_n,z_n$ とおく。$M$ は決定性なので、長さ $n$ の各文字列はちょうど 1 つの状態に行き着き、
$$x_n+y_n+z_n=2^n(1)$$
が成り立つ。求めるものは $y_n$ であり、空列は初期状態 $p$ にとどまるので $x_0=1,y_0=0,z_0=0$ である。

漸化式. 表から状態 $q$ に入る遷移は「$p$ から $a$」と「$r$ から $b$」の 2 本だけである。長さ $n+1$ の文字列は長さ $n$ の文字列に 1 文字付け加えたものなので
$$y_{n+1}=x_n+z_n.$$
$(1)$ を使うと
$$y_{n+1}=2^n-y_n(2)$$
となる。

漸化式を解く. $(2)$ の特殊解を $y_n=c\cdot 2^n$ の形で探すと、$2c\cdot 2^n=2^n-c\cdot 2^n$ より $3c=1$、$c=\frac{1}{3}$。そこで $u_n=y_n-\frac{2^n}{3}$ とおくと、$(2)$ から
$$u_{n+1}=-u_n$$
となり、$u_0=y_0-\frac{1}{3}=-\frac{1}{3}$ なので $u_n=-\frac{(-1{)}^n}{3}$。よって
$$y_n=\frac{2^n-(-1{)}^n}{3}.$$

確認. $n=0$: $0$ 個（空列は $p$ で終わる）。$n=1$: $a$ のみで $1$ 個、式は $\frac{2+1}{3}=1$。$n=2$: $aa\to r$, $ab\to p$, $ba\to p$, $bb\to q$ より $1$ 個、式は $\frac{4-1}{3}=1$。$n=3$: 式は $\frac{8+1}{3}=3$ で、実際 $aab,aba,baa$ の 3 個が受理される。

（別解: $p,q,r$ を $0,1,2$ とみると、$a$ は $+1$、$b$ は $-1$（$\mathrm{mod}3$）の遷移であり、受理されるのは「$a$ の個数 $-$ $b$ の個数 $\equiv 1(\mathrm{mod}3)$」の文字列である。）

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

状態を $p=0,q=1,r=2$（mod 3）と対応させる。表より、a を読むと $p\to q,q\to r,r\to p$ となり、状態は $+1$ される。b を読むと $p\to r,q\to p,r\to q$ となり、状態は $+2$ される（$0+2=2,1+2=3\equiv 0,2+2=4\equiv 1$）。したがって文字列 $w$ を読んだあとの状態は $|w{|}_a+2|w{|}_b\mathrm{mod}3$ で、受理するのはこれが $1$ のときである。

長さ $n$ の文字列は、各位置で $+1$ か $+2$ を選ぶ列と一対一に対応する。和が $1(\mathrm{mod}3)$ になる個数 $f(n)$ を、1 の 3 乗根 $\omega =e^{2\pi i/3}$ を使って数える。
$$f(n)=\frac{1}{3}\sum _{k=0}^2{\omega }^{-k}{\left({\omega }^k+{\omega }^{2k}\right)}^n.$$
$k=0$ の項は $2^n$。$k=1,2$ では ${\omega }^k+{\omega }^{2k}=-1$ なので、
$$f(n)=\frac{1}{3}\left[2^n+(-1{)}^n({\omega }^{-1}+{\omega }^{-2})\right]=\frac{2^n-(-1{)}^n}{3}$$
（${\omega }^{-1}+{\omega }^{-2}={\omega }^2+\omega =-1$）。

別の方法として漸化式でも確かめる。$x_n,y_n,z_n$ を長さ $n$ の文字列で状態 $0,1,2$ に至る個数とすると、$x_{n+1}=y_n+z_n$ などが成り立ち、各 $n\ge 1$ で $x_n+y_n+z_n=2^n$。$n$ ごとに $x_n=y_n$ か $z_n=y_n$ のように 2 つの値が一致し、$y_n=(2^n-(-1{)}^n)/3$ に落ち着く。

検算。$n=0$: $0$（空列は $p$ に留まり $q$ でない）。$n=1$: $1$（a のみ）。$n=2$: $(4-1)/3=1$（bb のみ。aa は $r$、ab と ba は $p$）。$n=3$: $(8+1)/3=3$（aab, aba, baa は a が 2 個・b が 1 個で $2+2=4\equiv 1$ となり、他に bbb は $6\equiv 0$、aaa は $3\equiv 0$、abb, bab, bba は $1+4=5\equiv 2$）で 3 個。いずれも一致する。

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