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

生成される言語の形. $A$ からは $a$ しか生成されない。$S$ に規則 $S\to AS$ を使うと左に $a$ が 1 つ、$S\to SA$ を使うと右に $a$ が 1 つ付き、最後に $S\to b$ で終わる。したがって $S$ の構文木は、根から伸びる $S$ の鎖に沿って「左に $a$ を付ける（L）」「右に $a$ を付ける（R）」を何回か選び、最後に $b$ を置いたものである。L を $i$ 回、R を $j$ 回使うと、生成される文字列は $a^{i}b{a}^j$ になる。

対応の確認. 逆に、構文木はこの L, R の並び（長さ $i+j$ の列）で完全に決まり、異なる列からは異なる構文木ができる（$S$ の鎖の各段で使った規則が異なるから）。

数え上げ. $w=aabaa$ は $i=2$, $j=2$ の場合なので、構文木の個数は、長さ 4 の列で L を 2 個・R を 2 個並べる方法の数に等しく
$$\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6.$$

CYK 法による検算. 部分文字列 $w[k..l]$ から $S$ を導出する構文木の個数を $N(k,l)$ とする（$w=w_1\cdots w_5$, $w_3=b$）。$S$ の部分木は必ず $b$ を含むので、$k\le 3\le l$ のときだけ $N\ne 0$ で、$N(3,3)=1$、$N(k,l)=N(k+1,l)+N(k,l-1)$（左端の $a$ を $A$ に、または右端の $a$ を $A$ に分ける。ほかの分割では片側が $a$ の列になり $A$ の 1 文字か $S$ にならない）。これより
$N(2,3)=1$, $N(3,4)=1$, $N(1,3)=1$, $N(3,5)=1$, $N(2,4)=2$, $N(1,4)=3$, $N(2,5)=3$, $N(1,5)=N(2,5)+N(1,4)=6$ となり、一致する。

答え: $6$

この文法で $S$ から導出される文字列は $a^{i}b{a}^j$ の形である。$S\to b$ を使うと $b$ が 1 つだけ生じ、$S\to SA$ は右に $a$ を、$S\to AS$ は左に $a$ を 1 つ付け加えるからである（$A\to a$ のみ）。

$w=aabaa$ は $b$ の左に $a$ が 2 個、右に $a$ が 2 個ある。構文木は、根から順に $S\to SA$（右端の $a$ を外側から取り除く）か $S\to AS$（左端の $a$ を取り除く）のどちらを使うかの列で決まる。最終的に $S\to b$ で終わるまでに規則を 4 回使い、そのうち $S\to AS$ が 2 回、$S\to SA$ が 2 回である。この列と構文木は 1 対 1 に対応する（異なる列は根に近い側の最初に異なる位置で、異なる木を与える）。

よって個数は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$。

検算: 一般に $a^{i}b{a}^j$ の構文木の個数は $\left(\genfrac{}{}{0ex}{}{i+j}{i}\right)$ で、$i=j=1$ のとき $\left(\genfrac{}{}{0ex}{}{2}{1}\right)=2$（$S\to SA$ 先か $S\to AS$ 先か）となり、手で数えた結果と一致する。