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

部分文字列ごとに数える（CYK 法の考え方）　$S$ から導出できる文字列を調べる。$A,B$ はそれぞれ $a,b$ だけを導出する。$S\to AB$ は $ab$ を、$S\to AS$ は「$a$ + $S$ から導出できる文字列」を、$S\to SB$ は「$S$ から導出できる文字列 + $b$」を作るので、$S$ から導出できる文字列は $a^i{b}^j$（$i\ge 1,j\ge 1$）の形に限られる。

そこで $f(i,j)$ を「$a^i{b}^j$ に対する、根が $S$ の構文木の個数」とする（$i=0$ または $j=0$ のときは $f=0$）。$a^i{b}^j$ を根で 2 つに分ける方法を規則ごとに見ると、
- $S\to AB$：左が $A$ で $a$、右が $B$ で $b$ なので、$i=j=1$ のときだけ使え、1 通り。
- $S\to AS$：左の $A$ が先頭の $a$ を導出し、右の $S$ が $a^{i-1}{b}^j$ を導出する。$f(i-1,j)$ 通り。
- $S\to SB$：右の $B$ が末尾の $b$ を導出し、左の $S$ が $a^i{b}^{j-1}$ を導出する。$f(i,j-1)$ 通り。

異なる規則や異なる分け方からは異なる構文木ができるので
$$f(1,1)=1,f(i,j)=f(i-1,j)+f(i,j-1)((i,j)\ne (1,1))$$
となる。

表を埋める

例えば $f(1,2)=f(0,2)+f(1,1)=0+1=1$、$f(2,2)=f(1,2)+f(2,1)=1+1=2$、$f(2,3)=f(1,3)+f(2,2)=1+2=3$、$f(3,3)=f(2,3)+f(3,2)=3+3=6$ である。

（CYK 表で見ると、$w=aaabbb$ の部分文字列のうち $S$ を含むのは $a^i{b}^j$（$i,j\ge 1$）の形のものだけで、その各マスについて「分け方ごとの構文木の数の積の和」を求めたものが上の表になっている。）

よって $w=aaabbb$ の構文木の個数は $f(3,3)=6$ である。

（別の見方：根から下へ、$S\to AS$ で $a$ を 1 個、$S\to SB$ で $b$ を 1 個ずつはがし、最後に $S\to AB$ で終わる。$a$ を 2 回、$b$ を 2 回はがす順番の数なので $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ となり、一致する。）

$S$ から導出できる文字列は $a^i{b}^j$（$i,j\ge 1$）の形だけである。$f(i,j)$ を $S$ から $a^i{b}^j$ への構文木の個数とする。$A\to a$、$B\to b$ は一意なので、根の規則で場合分けする。

• $S\to AB$：$a^i{b}^j=ab$、すなわち $(i,j)=(1,1)$ のときだけ使え、1 通り。
• $S\to AS$：先頭の $a$ が $A$、残りが $S$ から導出される。$i\ge 2$ のとき $f(i-1,j)$ 通り。
• $S\to SB$：末尾の $b$ が $B$、残りが $S$ から導出される。$j\ge 2$ のとき $f(i,j-1)$ 通り。

よって $f(1,1)=1$、それ以外は $f(i,j)=[i\ge 2]f(i-1,j)+[j\ge 2]f(i,j-1)$。これは $(1,1)$ から $(i,j)$ へ右・上に進む格子経路の数で、$f(i,j)=\left(\genfrac{}{}{0ex}{}{i+j-2}{i-1}\right)$。

表で確認する（行 $i$、列 $j$）：
$f(1,1)=1,f(1,2)=1,f(1,3)=1$、
$f(2,1)=1,f(2,2)=2,f(2,3)=3$、
$f(3,1)=1,f(3,2)=3,f(3,3)=f(2,3)+f(3,2)=6$。

検算：$\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$。$aabbb$ などの小さい場合 $f(2,2)=2$（$A(SB)$ 型と $(AS)B$ 型、$aabb$ の 2 通り）とも整合する。よって答えは 6。