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

方針：ブロックへの分解で漸化式を作る。

$L(r)$ の文字列は、ブロック $a$（長さ $1$）とブロック $bb$（長さ $2$）を $0$ 個以上並べたものです。

分解が一通りであることの確認. 文字列を左から読むとき、$a$ が来ればそれはブロック $a$、$b$ が来ればそれはブロック $bb$ の先頭なので、次の文字と合わせて $bb$ とするしかありません。したがって $L(r)$ の各文字列のブロックへの分け方はただ一通りです。よって「ブロックの並べ方」を数えれば、文字列を重複なく数えられます。

漸化式. $L(r)$ に属する長さ $k$ の文字列の個数を $c_k$ とします。長さ $k(k\ge 2)$ の文字列を、最後のブロックで分けます（和の法則）。
- 最後のブロックが $a$ のとき：残りは長さ $k-1$ の $L(r)$ の文字列で、$c_{k-1}$ 通り。
- 最後のブロックが $bb$ のとき：残りは長さ $k-2$ の $L(r)$ の文字列で、$c_{k-2}$ 通り。

よって
$$c_k=c_{k-1}+c_{k-2}(k\ge 2).$$

初期値. 長さ $0$ の文字列は空列 $\epsilon$（ブロック $0$ 個）だけなので $c_0=1$。長さ $1$ の文字列は $a$ だけ（$b$ 単独は不可）なので $c_1=1$。

順に計算.
$$\begin{array}{rlrlrl}{c}_2& =1+1=2,& c_3& =2+1=3,& c_4& =3+2=5,\\ c_5& =5+3=8,& c_6& =8+5=13,& c_7& =13+8=21,\\ c_8& =21+13=34,& c_9& =34+21=55,& c_{10}& =55+34=89.\end{array}$$

（確認：$c_2=2$ は $aa,bb$ の $2$ 個、$c_3=3$ は $aaa,abb,bba$ の $3$ 個で、直接数えた結果と一致します。）

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

$L(r)$ は文字列 $a$ と $bb$ を任意に連結してできる文字列全体である。この分解は一意である。理由は、文字列を左から読むと、$a$ なら $a$ のブロック、$b$ なら次も $b$ でなければならず $bb$ のブロックになるからである。したがって、長さ $n$ の文字列の個数 $f(n)$ は、長さ $1$ の $a$ と長さ $2$ の $bb$ の並べ方の個数に等しい。

漸化式は $f(n)=f(n-1)+f(n-2)$ である。初期値は $f(0)=1$（空列）、$f(1)=1$（$a$）。

計算すると
$f(2)=2$, $f(3)=3$, $f(4)=5$, $f(5)=8$, $f(6)=13$, $f(7)=21$, $f(8)=34$, $f(9)=55$, $f(10)=89$。

検算として、$bb$ を $k$ 個使う場合を数える。$a$ は $10-2k$ 個で、ブロックの総数は $10-k$ 個。並べ方は $\left(\genfrac{}{}{0ex}{}{10-k}{k}\right)$ 通りで、$k=0,\dots ,5$ について
$1+9+28+35+15+1=89$。

よって答えは $89$。