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

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

$L(r)$ の文字列は、ブロック $a$（長さ $1$）とブロック $bb$（長さ $2$）を好きな順に好きな個数だけ並べたものです。

分解が一通りであることの確認　文字列を先頭から読むと、先頭が $a$ ならば最初のブロックは $a$ に決まり、先頭が $b$ ならば最初のブロックは $bb$ に決まります（$b$ で始まるブロックは $bb$ だけだからです）。したがって $L(r)$ の各文字列は、ブロックの並べ方とちょうど一対一に対応します。よって「長さ $n$ の文字列の個数」は「長さの合計が $n$ になるブロックの並べ方の個数」に等しくなります。

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

したがって
$$f(n)=f(n-1)+f(n-2)(n\ge 2)$$
です。初期値は、空列だけの $f(0)=1$、文字列 $a$ だけの $f(1)=1$ です。

順に計算する
$$\begin{array}{rlrlrl}f(2)& =1+1=2,& f(3)& =2+1=3,& f(4)& =3+2=5,\\ f(5)& =5+3=8,& f(6)& =8+5=13,& f(7)& =13+8=21,\\ f(8)& =21+13=34,& f(9)& =34+21=55,& f(10)& =55+34=89.\end{array}$$

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

よって求める個数は $89$ です。

$L(r)$ は $a$ と $bb$ を並べてできる文字列全体である。$a$ は長さ 1、$bb$ は長さ 2 のブロックである。

$a_n$ を長さ $n$ の文字列で $L(r)$ に属するものの個数とする。

文字列を $a$ と $bb$ のブロックに分ける方法は一意である。実際、$b$ は必ず次の $b$ と対になって $bb$ になり、$a$ は単独のブロックになる。したがって、長さ $n$ の文字列の個数はブロック列の個数に等しい。

最初のブロックで場合分けすると、$a_n=a_{n-1}+a_{n-2}$ が成り立つ。初期値は $a_0=1$（空列）、$a_1=1$（$a$）である。

順に計算する。
$a_2=2$（$aa$, $bb$）
$a_3=3$
$a_4=5$
$a_5=8$
$a_6=13$
$a_7=21$
$a_8=34$
$a_9=55$
$a_{10}=89$

検算として、長さ 4 の文字列を数える。ブロックの分け方は $aaaa$, $bbaa$, $abba$, $aabb$, $bbbb$ の 5 通りで、$a_4=5$ と一致する。

よって答えは 89 である。