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

長さ $n$ の文字列 $3^n$ 個それぞれについて、$p$ から読み終えたときの状態を考えます。最後に状態 $p,q,r,s$ にいる文字列の個数を、それぞれ $P_n,Q_n,R_n,S_n$ とおきます。初期状態は $p$ なので、$P_0=1,Q_0=R_0=S_0=0$ です。

遷移の構造

状態 $p,q,r,s$ を $0,1,2,3$ と番号づけると、表から次のことが読み取れます。

• $a$ は番号を $1$ 増やす
• $b$ は番号を $1$ 減らす
• $c$ は番号を変えない

ここで番号は $4$ を法として考えます。したがって $M$ は「($a$ の個数)$-$($b$ の個数)$\equiv 0(\mathrm{mod}4)$」となる文字列を受理します。

漸化式

各状態に入る遷移を表から数えると、次の漸化式が得られます。
$$P_{n+1}=P_n+Q_n+S_n,Q_{n+1}=Q_n+P_n+R_n,$$
$$R_{n+1}=R_n+Q_n+S_n,S_{n+1}=S_n+R_n+P_n.$$

$a$ と $b$ を入れかえる対称性（または漸化式と初期値を比べること）から、すべての $n$ で $Q_n=S_n$ です。そこで $x_n=P_n,y_n=Q_n=S_n,z_n=R_n$ とおくと、
$$x_{n+1}=x_n+2y_n,y_{n+1}=x_n+y_n+z_n,z_{n+1}=z_n+2y_n$$
となります。

漸化式を解く

(1) 全体の個数について、$x_n+2y_n+z_n=3^n$ です。

(2) $x_{n+1}-z_{n+1}=x_n-z_n$ なので、$x_n-z_n=x_0-z_0=1$ です。

(3) (1) より $x_n+z_n=3^n-2y_n$ です。これを $y$ の漸化式に代入すると
$$y_{n+1}=y_n+3^n-2y_n=3^n-y_n$$
となります。特殊解として $y_n=\frac{3^n}{4}$ をとると、$\frac{3^{n+1}}{4}=3^n-\frac{3^n}{4}$ が成り立ちます。一般解は $y_n=\frac{3^n}{4}+C(-1{)}^n$ と書けます。$y_0=0$ より $C=-\frac{1}{4}$ なので、
$$y_n=\frac{3^n-(-1{)}^n}{4}$$
です。

(4) $x_n+z_n=3^n-2y_n=\frac{3^n+(-1{)}^n}{2}$ と $x_n-z_n=1$ を足して $2$ で割ると、
$$x_n=\frac{3^n+(-1{)}^n+2}{4}$$
が得られます。

確認

• $n=0$：値は $1$ で、空文字列のみです。
• $n=1$：値は $1$ で、$c$ のみです。
• $n=2$：値は $3$ で、$cc,ab,ba$ です。

いずれも直接数えた結果と一致します。

よって、求める個数は $\frac{3^n+(-1{)}^n+2}{4}$ です。

状態を $p=0,q=1,r=2,s=3$ と $\mathbb{Z}/4$ の元に対応させる。表から、$a$ は状態を $+1$、$b$ は $-1$、$c$ は $0$ 動かすことが分かる（$b$: $p\to s,q\to p,r\to q,s\to r$）。したがって文字列を読んだ後の状態は ($a$ の個数 $-$ $b$ の個数) mod 4 で決まる。初期状態も受理状態も $p=0$ なので、受理されるのは $\#a-\#b\equiv 0(\mathrm{mod}4)$ となる文字列である。

1 の 4 乗根の判別式（単位根フィルター）を使う。$\omega =i$ として、求める個数は
$\frac{1}{4}{\sum }_{k=0}^3(1+i^k+i^{-k}{)}^n$。
各項は $k=0$: $3^n$、$k=1$: $(1+i-i{)}^n=1$、$k=2$: $(1-1-1{)}^n=(-1{)}^n$、$k=3$: $1$。
よって個数は $\frac{3^n+2+(-1{)}^n}{4}$。

検算: $n=0$ は $(1+2+1)/4=1$（空列）。$n=1$ は $(3+2-1)/4=1$（$c$ のみ）。$n=2$ は $(9+2+1)/4=3$（$cc,ab,ba$）で、直接数えた結果と一致する。