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

規則 $A\to a$, $B\to b$, $C\to SB$ をまとめると、$S$ の規則は実質的に
$$S\to SS\mid ab\mid aSb$$
である。したがって $S$ から導かれる文字列は、$a$ を開き括弧、$b$ を閉じ括弧とみたときの空でない「括弧の対応がとれた文字列」である。

部分文字列 $u$ に対し、$S$ を根として $u$ を導く導出木の個数を $N(u)$ とおく（CYK 法の表の各欄に、非終端記号 $S$ の導出木の個数を書き込むことに相当する）。

(1) $w$ の分解. 括弧の深さを左から数えると、$w$ は深さが $0$ に戻る位置で
$$w=\underset{p_1}{\underbrace{ab}}\underset{p_2}{\underbrace{ab}}\underset{p_3}{\underbrace{aabb}}\underset{p_4}{\underbrace{ab}}$$
の $4$ つのブロックに分かれる。各ブロックは、それ以上「対応のとれた 2 つの空でない文字列の連結」に分けられない。

(2) 各ブロックの導出木の個数.
- $p=ab$: $S\to AB$ のみが使える（$S\to SS$ は長さ $1$ の $S$ が存在しないので不可、$S\to AC$ は $C$ が長さ $1$ の文字列を導けないので不可）。よって $N(ab)=1$。
- $p=aabb$: $S\to AC$ で $a\cdot (abb)$ とし、$C\to SB$ で $(ab)\cdot b$ とする。内側の $ab$ は $N(ab)=1$ 通り。$S\to SS$ は $aa\cdot bb$, $a\cdot abb$, $aab\cdot b$ のどの分け方でも両側が $S$ から導けないので不可。$S\to AB$ は長さ $2$ のときだけ。よって $N(aabb)=1$。

(3) 連結部分の導出木の個数. 2 つ以上のブロックの連結 $u=p_i{p}_{i+1}\cdots p_j$ では、根の規則は $S\to SS$ に限る（$S\to AC$ を使うと $u=avb$ で $v$ が対応のとれた文字列になり、$u$ が 1 ブロックになってしまう）。$S\to SS$ で分けるとき、左右がともに $S$ から導けるのはブロックの境目で分けるときだけなので
$$N(p_i\cdots p_j)=\sum _{k=i}^{j-1}N(p_i\cdots p_k)N(p_{k+1}\cdots p_j)$$
が成り立つ。各ブロックで $N(p_i)=1$ であるから、ブロックの個数を $m$ として $T_m=N(\text{ブロック }m\text{ 個の連結})$ とおくと
$$T_1=1,T_2=T_1{T}_1=1,T_3=T_1{T}_2+T_2{T}_1=2,$$
$$T_4=T_1{T}_3+T_2{T}_2+T_3{T}_1=2+1+2=5.$$

$w$ は $4$ ブロックの連結なので、導出木の個数は $T_4=5$ である（これはカタラン数 $C_3=5$ に等しい）。

答え: $5$

$A\to a$, $B\to b$ なので、$a$ を開き括弧、$b$ を閉じ括弧とみなす。$C\to SB$ を $AC$ に代入すると、$S$ の規則は実質 $S\to SS\mid ab\mid aSb$ と同じで、各導出木はこれらの規則の適用に一対一に対応する（$AC$ は $aSb$、$AB$ は $ab$）。

$S$ から導出される文字列は空でない釣り合った括弧列だけである。$w=ababaabbab$ は $()()(())()$ で、原始的な（それ以上分けられない）ブロックに分けると
$$w=(ab)(ab)(aabb)(ab)$$
の 4 個になる。

1. $S\to SS$ の分割は、左右とも釣り合った文字列になる位置、すなわちブロックの境界でしか起こらない。
2. 各ブロックの導出木の個数はどれも 1 である。$ab$ は $S\to AB$ のみ。$aabb$ は $S\to AC$, $C\to SB$ で内側の $S$ が $ab$ を導出する 1 通りのみ。
3. したがって、ブロック 4 個を $SS$ の二分木で結ぶ方法の数、すなわち 4 個の積の括弧付けの数が答えになる。これはカタラン数 $C_3=\frac{1}{4}\left(\genfrac{}{}{0ex}{}{6}{3}\right)=5$ である。

検算として CYK で数える。$w=w_1\cdots w_{10}$ に対し、部分列 $w_i\cdots w_j$ の木の個数を $s(i,j)$ とすると、$s(i,j)={\sum }_{k}s(i,k)s(k+1,j)+[w_i=a][w_j=b]s(i+1,j-1)$（$j=i+1$ のとき最後の項は 1）である。$(ab)(ab)(ab)$ 型の 3 ブロックは 2 通り、4 ブロックは $2+1+2=5$ 通り（分割点が 1 個目・2 個目・3 個目の後のとき、それぞれ $1\cdot 2$、$1\cdot 1$、$2\cdot 1$）で、上の結果と一致する。

答え: 5