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

状態の意味. 状態 $p,q,r,s$ にそれぞれ $0,1,2,3\in \mathbb{Z}/4\mathbb{Z}$ を対応させると、表から
$$\delta (i,a)=i+1,\delta (i,b)=i+2,\delta (i,c)=i(\mathrm{mod}4)$$
となっている（例: $\delta (r,b)=p$ は $2+2\equiv 0$）。初期状態は $0$ なので、文字列 $w$ を読んだ後の状態は
$$|w{|}_a+2|w{|}_b\mathrm{mod}4$$
であり、$w$ が受理されるのはこの値が $0$ または $1$ のときである。

数え上げ（1 の 4 乗根によるフィルター）. 長さ $n$ の文字列全体について $x^{|w{|}_a+2|w{|}_b}$ を足し合わせると、各文字が独立に $a\mapsto x$, $b\mapsto x^2$, $c\mapsto 1$ を与えるので
$$\sum _{|w|=n}{x}^{|w{|}_a+2|w{|}_b}=(1+x+x^2{)}^n.$$
値が $\equiv r(\mathrm{mod}4)$ となる文字列の個数を $N_r$ とすると、$\omega =i$（虚数単位）として
$$N_r=\frac{1}{4}\sum _{k=0}^3{\omega }^{-kr}{\left(1+{\omega }^k+{\omega }^{2k}\right)}^n.$$
各 $k$ について $1+{\omega }^k+{\omega }^{2k}$ を計算すると
- $k=0$: $3$
- $k=1$: $1+i-1=i$
- $k=2$: $1-1+1=1$
- $k=3$: $1-i-1=-i$

したがって
$$N_0=\frac{1}{4}\left(3^n+i^n+1+(-i{)}^n\right),$$
$$N_1=\frac{1}{4}\left(3^n+i^{-1}{i}^n+i^{-2}\cdot 1+i^{-3}(-i{)}^n\right)=\frac{1}{4}\left(3^n+i^{n-1}-1+(-i{)}^{n-1}\right).$$
（$i^{-3}=i$, $i\cdot (-i{)}^n=(-i{)}^{n-1}\cdot i\cdot (-i)=(-i{)}^{n-1}$ を使った。）
$i^m+(-i{)}^m=2\cos \frac{m\pi }{2}$ より
$$N_0=\frac{3^n+1+2\cos \frac{n\pi }{2}}{4},N_1=\frac{3^n-1+2\cos \frac{(n-1)\pi }{2}}{4}=\frac{3^n-1+2\sin \frac{n\pi }{2}}{4}.$$
よって受理される文字列の個数は
$$N_0+N_1=\frac{3^n+\cos \frac{n\pi }{2}+\sin \frac{n\pi }{2}}{2}.$$

（別解: 遷移行列 $A$ は $4\times 4$ の巡回行列で、その固有値は $1+{\omega }^k+{\omega }^{2k}$, すなわち $3,i,1,-i$ である。これは上の計算と同じことを表している。）

確認. $n=1$: 式は $\frac{3+0+1}{2}=2$。実際 $a$（値 $1$）, $c$（値 $0$）が受理され、$b$（値 $2$）は受理されない。$n=2$: 式は $\frac{9-1+0}{2}=4$。実際 $ac,ca$（値 $1$）, $bb,cc$（値 $0$）の 4 個で、他の 5 個（$aa,bc,cb$ は値 $2$、$ab,ba$ は値 $3$）は受理されない。

遷移表を見ると、状態 $p,q,r,s$ を $0,1,2,3$ と対応させたとき、文字 $a$ は $+1$、$b$ は $+2$、$c$ は $+0$（いずれも $\mathrm{mod}4$）を加える遷移になっている（例: $p\stackrel{a}{\to }q$, $q\stackrel{a}{\to }r$, $s\stackrel{a}{\to }p$; $p\stackrel{b}{\to }r$, $q\stackrel{b}{\to }s$, $r\stackrel{b}{\to }p$, $s\stackrel{b}{\to }q$; $c$ は自己ループ）。

よって文字列を読み終えたときの状態は、各文字に重み $a\mapsto 1,b\mapsto 2,c\mapsto 0$ を割り当てた総和を $4$ で割った余りで決まる。初期状態は $0$（$p$）、受理状態は $p,q$ すなわち余り $0$ または $1$。

長さ $n$ の文字列で総和が $k(\mathrm{mod}4)$ のものの個数を $N_k$ とする。$f(\omega )=1+\omega +{\omega }^2$ として
$$N_k=\frac{1}{4}\sum _{j=0}^3{i}^{-jk}f(i^j{)}^n.$$
$f(1)=3,f(i)=i,f(-1)=1,f(-i)=-i$。

$N_0+N_1=\frac{1}{4}[2\cdot 3^n+(i^n(1-i)+(-i{)}^n(1+i))+(1-1)]$

$j=2$ の項は $k=0,1$ で $1+(-1)=0$。$j=1,3$ の項は互いに共役で、
$i^n(1-i)+\overline{i^n(1-i)}=2\mathrm{Re}(i^n(1-i))=2(\cos \frac{n\pi }{2}+\sin \frac{n\pi }{2})$。

ゆえに
$$N_0+N_1=\frac{3^n+\cos \frac{n\pi }{2}+\sin \frac{n\pi }{2}}{2}.$$

検算: $n=1$ のとき $a,c$ が受理（$p\to q$, $p\to p$）、$b$ は $r$ で非受理なので $2$ 個。式は $(3+0+1)/2=2$ で一致。$n=2$ のとき総和が $0$: $(c,c),(b,b)$、総和が $1$: $(a,c),(c,a)$ の $4$ 個。式は $(9-1+0)/2=4$ で一致。