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

方針：CYK 法の表に「個数」を記録する。

CYK 法では、$w$ の各部分文字列について、それを導出できる非終端記号を表に書き込む。ここでは記号だけでなく、その記号を根とする構文木の個数も記録する。構文木と最左導出は 1 対 1 に対応するので、$S$ を根とする $w$ の構文木の個数を数えればよい。

$w=aaabbbbb$ の部分文字列のうち $A$ または $B$ 以外の非終端記号が導出しうるのは $a^p{b}^q$（$p\ge 1,q\ge 1$）の形のものだけである（$b$ の後に $a$ が来る部分文字列は、どの規則の右辺も「$a$ 側の記号が左、$b$ 側の記号が右」なので導出できない）。そこで部分文字列 $a^p{b}^q$ から $S$, $T$ を根とする構文木の個数を $N_S(p,q)$, $N_T(p,q)$ と書く。

分割の考え方. 長さ $2$ 以上の部分文字列を左右 2 つに分けるとき、
- $S\to AB$：左が $A$（1 文字 $a$）、右が $B$（1 文字 $b$）なので、$p=q=1$ のときだけ $1$ 通り。
- $S\to AT$：左が先頭の $a$ 1 文字、右の $a^{p-1}{b}^q$ を $T$ が導出する。$T$ は $SB$ から始まるので $a$ を 1 個以上含む必要があり、$p\ge 2$ のときだけ $N_T(p-1,q)$ 通り。
- $S\to SB$：右が末尾の $b$ 1 文字、左の $a^p{b}^{q-1}$ を $S$ が導出するので $N_S(p,q-1)$ 通り（$q-1\ge 1$ が必要）。
- $T\to SB$：同様に $N_T(p,q)=N_S(p,q-1)$。

よって
$$N_S(p,q)=[p=q=1]+N_T(p-1,q)+N_S(p,q-1),N_T(p,q)=N_S(p,q-1)$$
（$[p=q=1]$ は $p=q=1$ のとき $1$、それ以外は $0$。定義されない項は $0$ とする）。

表を短い部分文字列から埋める.
- $N_S(1,1)=1$（$S\to AB$）。
- $N_S(1,q)=N_S(1,q-1)=\cdots =1$（$q\ge 1$）。$N_S(p,q)=0$（$q<p$）であることも同様にわかる。
- $N_S(2,2)=N_T(1,2)+N_S(2,1)=N_S(1,1)+0=1$
- $N_S(2,3)=N_T(1,3)+N_S(2,2)=N_S(1,2)+1=1+1=2$
- $N_S(2,4)=N_T(1,4)+N_S(2,3)=N_S(1,3)+2=1+2=3$
- $N_S(3,3)=N_T(2,3)+N_S(3,2)=N_S(2,2)+0=1$
- $N_S(3,4)=N_T(2,4)+N_S(3,3)=N_S(2,3)+1=2+1=3$
- $N_S(3,5)=N_T(2,5)+N_S(3,4)=N_S(2,4)+3=3+3=6$

したがって $w=a^3{b}^5$ の構文木は $N_S(3,5)=6$ 通りである。

確認. 構文木は、中心の $ab$（$S\to AB$）から始めて「外側に $a\cdots b$ を付ける操作（$S\to AT,T\to SB$）」と「右に $b$ を付ける操作（$S\to SB$）」を順に施したものとみなせる。$a^3{b}^5$ では前者が $2$ 回、後者が $5-1-2=2$ 回で、その並べ方は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通りとなり一致する。

答え：$6$

文字列 $a^i{b}^j$ を $S$ から導出する構文木の数を $s(i,j)$、$T$ から導出する構文木の数を $t(i,j)$ とおく。$S,T$ はともに空列を導出しないので、$i\ge 1,j\ge 1$ でなければ $s(i,j)=0$、$t(i,j)=0$ とする。また生成規則から導出される文字列はすべて $a^i{b}^j$ の形である。

$T\to SB$ より $t(i,j)=s(i,j-1)$。

$S$ の各規則について考える。
- $S\to AB$ は $ab$ のときだけ使え、寄与は $[i=1,j=1]$。
- $S\to AT$ の寄与は $t(i-1,j)=s(i-1,j-1)$。
- $S\to SB$ の寄与は $s(i,j-1)$。

よって次の漸化式を得る。
$$s(i,j)=[i=1,j=1]+s(i-1,j-1)+s(i,j-1).$$

$i=1$ のとき、$s(1,1)=1$ であり、$j\ge 2$ では $s(1,j)=s(1,j-1)$ なので $s(1,j)=1$。

$i=2$ のとき、$s(2,1)=0$、$s(2,2)=s(1,1)+s(2,1)=1$、$s(2,3)=s(1,2)+s(2,2)=2$、$s(2,4)=1+2=3$、$s(2,5)=1+3=4$。

$i=3$ のとき、$s(3,1)=0$、$s(3,2)=s(2,1)+s(3,1)=0$、$s(3,3)=s(2,2)+s(3,2)=1$、$s(3,4)=s(2,3)+s(3,3)=2+1=3$、$s(3,5)=s(2,4)+s(3,4)=3+3=6$。

したがって $w=aaabbbbb$ の構文木は $6$ 通りである。

検算として、$S\to SB$ を何回使うかで場合分けする。この文法の構文木は、根から $S\to SB$ を繰り返し使い、最後に $S\to AB$ か $S\to AT$ に至る構造をしており、$a$ を 1 つ消費するたびに $b$ が 1 つ対応づけられる。$a$ が 3 個、$b$ が 5 個のとき、$a$ ごとの $b$ の置き方の数え上げは漸化式の結果と一致する。

文法が構文木ごとに異なる最左導出を与えるので、最左導出の個数も $6$ である。