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

$a$ を開き括弧、$b$ を閉じ括弧とみなすと、$G$ が生成する言語 $L(G)$ は「空でない、括弧の対応がとれた文字列」全体である。

準備: 分解できない文字列

$L(G)$ の文字列 $u$ のうち、どの真の接頭辞（空でも $u$ 全体でもない接頭辞）も $a$ と $b$ の個数が等しくならないものを「素な文字列」とよぶ。

• 素な文字列 $u$ に $S\to SS$ を最初に使うことはできない。$SS$ から $u=u_1{u}_2$（$u_1,u_2\in L(G)$）と分けると、$u_1$ は $a,b$ の個数が等しい真の接頭辞になってしまうからである。したがって $u$ の導出木の根では $S\to ab$（$u=ab$ のとき）か $S\to aSb$ が使われる。$S$ は空文字列を生成しないので、$u=ab$ のときは $S\to ab$ だけが使え、$u\ne ab$ のときは $S\to aSb$ だけが使える。
• 素でない文字列は、$a,b$ の個数が等しくなる位置で切ると、素な文字列の並び $u_1{u}_2\cdots u_k$（$k\ge 2$）にただ 1 通りに分解される。このとき $S\to aSb$ や $S\to ab$ は根に使えない（両端が $a\cdots b$ の 1 組に対応しないため）ので、根からは $S\to SS$ を繰り返して $k$ 個の $S$ に分け、それぞれが $u_i$ を導出する。$S\to SS$ による分け方の個数は、葉が $k$ 個の全二分木の個数、すなわちカタラン数 $C_{k-1}=\frac{1}{k}\left(\genfrac{}{}{0ex}{}{2k-2}{k-1}\right)$ である。

$w$ の分解

$w$ を左から読み、($a$ の個数) $-$ ($b$ の個数) を記録すると
$$1,2,1,2,1,2,1,0,1,0,1,0,1,0$$
となり、$0$ になる位置で区切ると
$$w=(aabababb)(ab)(ab)(ab)$$
と $4$ 個の素な文字列に分かれる。よって、この 4 つへの $S\to SS$ による分け方は $C_3=5$ 通りである。

各部分の導出木

• $ab$ の導出木は $S\to ab$ の $1$ 通り。
• $aabababb$ は素なので、根は $S\to aSb$ で、内側の $S$ が $ababab$ を導出する。$ababab=(ab)(ab)(ab)$ は $3$ 個の素な文字列に分かれ、それぞれの導出木は $1$ 通りなので、$ababab$ の導出木は $C_2=2$ 通り。よって $aabababb$ の導出木は $2$ 通り。

まとめ

導出木の個数は、外側の分け方と各部分の導出木の個数の積なので
$$5\times 2\times 1\times 1\times 1=10$$
である。

答え: $10$

$w=aabababbababab$ で $a$ を $+1$、$b$ を $-1$ とすると累積和は $1,2,1,2,1,2,1,0,1,0,1,0,1,0$ で、各接頭辞で 0 以上、最後に 0 となるのでダイク語（括弧列）である。0 に戻る位置は 8, 10, 12, 14 なので、既約な成分に分けると
$$w=(aabababb)(ab)(ab)(ab)$$

$G$ の導出木の数を $T(u)$ で表す。

(1) 既約成分 $u=avb$ について: 規則 $S\to SS$ は既約語の導出の根には使えない（既約語を 2 つの空でない文字列に分けるとどちらもダイク語にならない）。よって根は $S\to ab$（$v$ が空のとき、$T=1$）か $S\to aSb$（$v$ が空でないとき、$T(u)=T(v)$）。

(2) 既約成分が $k$ 個の語 $u_1\cdots u_k$（$k\ge 2$）について: 根は $S\to SS$ でなければならない。これは $k$ 個の成分を二分木状に括る方法に対応し、括り方は $k-1$ 番目のカタラン数 $C_{k-1}$ 通り、各成分の導出木は独立なので
$$T(u_1\cdots u_k)=C_{k-1}\prod _{i=1}^{k}T(u_i).$$
（$k=1$ のときは (1)。）

計算:
- 成分 $ab$: $T=1$。
- 成分 $aabababb=a(ababab)b$: 内側 $ababab$ は成分 3 個で各 $T=1$、$T(ababab)=C_2\cdot 1=2$。よって $T(aabababb)=2$。
- $w$ 全体: 成分 4 個、$C_3=5$、積は $2\cdot 1\cdot 1\cdot 1=2$。
$$T(w)=5\times 2=10.$$

検算: $C_2=2$（$(SS)S$ と $S(SS)$）、$C_3=5$ で、小さい例 $T(abab)=C_1=1$、$T(ababab)=2$ とも整合する。