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

方針 $L(r)$ の文字列は、ブロック $a$（長さ $1$）、$b$（長さ $1$）、$cc$（長さ $2$）を $0$ 個以上並べたものです。ブロックへの分解を使って、長さ $n$ の文字列の個数 $f(n)$ の漸化式を作ります。

分解が一通りであること 文字列の先頭の文字を見ると、最初のブロックが決まります。先頭が $a$ ならブロック $a$、$b$ ならブロック $b$、$c$ ならブロック $cc$ です（$c$ で始まるブロックは $cc$ だけ）。残りの部分にも同じことがくり返せるので、$L(r)$ の文字列のブロック分解はただ一通りです。したがって、文字列の個数はブロックの並べ方の個数と一致します。

漸化式 $f(n)$ を $L(r)$ に属する長さ $n$ の文字列の個数とします。$n\ge 2$ のとき、最初のブロックで場合分けします（和の法則）。
- 最初のブロックが $a$：残りは $L(r)$ に属する長さ $n-1$ の文字列で、$f(n-1)$ 個。
- 最初のブロックが $b$：同様に $f(n-1)$ 個。
- 最初のブロックが $cc$：残りは長さ $n-2$ の文字列で、$f(n-2)$ 個。

よって
$$f(n)=2f(n-1)+f(n-2)(n\ge 2)$$

初期値 長さ $0$ は空列（ブロック $0$ 個）の $1$ 個なので $f(0)=1$。長さ $1$ は $a,b$ の $2$ 個なので $f(1)=2$（$c$ 単独は $L(r)$ に属しません）。

計算
$$f(2)=2\cdot 2+1=5$$
（確認：$aa,ab,ba,bb,cc$ の $5$ 個）
$$f(3)=2\cdot 5+2=12$$
$$f(4)=2\cdot 12+5=29$$
$$f(5)=2\cdot 29+12=70$$
$$f(6)=2\cdot 70+29=169$$

したがって、求める個数は $169$ 個です。

$L(r)$ は、$a$、$b$、$cc$ を並べてできる文字列全体である。$c$ は必ず連続した偶数個で現れ、$c$ の連続部分（ラン）の長さが偶数であれば、その部分は $cc$ の列に一意に分解できる。よって、$L(r)$ の長さ $n$ の文字列の個数 $f(n)$ は、ブロック $a$、$b$（長さ1）と $cc$（長さ2）の並べ方の数に等しい。ブロックへの分解は一意なので重複は生じない。

漸化式は $f(n)=2f(n-1)+f(n-2)$、$f(0)=1$、$f(1)=2$ である。

$f(2)=2\cdot 2+1=5$
$f(3)=2\cdot 5+2=12$
$f(4)=2\cdot 12+5=29$
$f(5)=2\cdot 29+12=70$
$f(6)=2\cdot 70+29=169$

検算として、$cc$ の個数 $k$ で場合分けする。長さ6では $cc$ が $k$ 個、$a,b$ が $6-2k$ 個で、ブロック総数は $6-k$ である。$cc$ の位置の選び方は $\left(\genfrac{}{}{0ex}{}{6-k}{k}\right)$、$a,b$ の割り当ては $2^{6-2k}$ 通りである。

• $k=0$: $1\cdot 64=64$
• $k=1$: $5\cdot 16=80$
• $k=2$: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)\cdot 4=24$
• $k=3$: $\left(\genfrac{}{}{0ex}{}{3}{3}\right)\cdot 1=1$

合計は $64+80+24+1=169$ となり、漸化式の結果と一致する。