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

$w=w_1{w}_2{w}_3{w}_4{w}_5$ とし、$w_1=x,w_2=+,w_3=x,w_4=+,w_5=x$ とする。部分文字列 $w_{i..j}$ を非終端記号 $X$ から生成する導出木の個数を $N_X(i,j)$ と書く。CYK 法と同じく短い部分文字列から順に表を埋めるが、各欄には記号の集合ではなく導出木の個数を記録する。規則 $X\to YZ$ と分割位置 $k$（$i\le k<j$）について
$$N_X(i,j)=\sum _{X\to YZ}\sum _{k=i}^{j-1}{N}_Y(i,k)N_Z(k+1,j)$$
で計算する（分割位置と使う規則が違えば導出木の根の付近の形が違うので、重複なく数えられる）。以下、$0$ でない値だけを書く。

長さ 1：$E\to x$, $O\to +$ より
$N_E(1,1)=N_E(3,3)=N_E(5,5)=1$, $N_O(2,2)=N_O(4,4)=1$。

長さ 2：$E\to EP$ は $N_P(2,2)$ などが $0$ なのでどこでも $0$。$P\to OE$ より
$N_P(2,3)=N_O(2,2)N_E(3,3)=1\cdot 1=1$、$N_P(4,5)=N_O(4,4)N_E(5,5)=1$。
$(1,2),(3,4)$ の欄はすべて $0$。

長さ 3：
$N_E(1,3)=N_E(1,1)N_P(2,3)+N_E(1,2)N_P(3,3)=1\cdot 1+0=1$。
$N_E(3,5)=N_E(3,3)N_P(4,5)+N_E(3,4)N_P(5,5)=1+0=1$。
$(2,4)$ の欄：$N_P(2,4)=N_O(2,2)N_E(3,4)+N_O(2,3)N_E(4,4)=0$、$N_E(2,4)=0$。

長さ 4：
$N_E(1,4)=N_E(1,1)N_P(2,4)+N_E(1,2)N_P(3,4)+N_E(1,3)N_P(4,4)=0+0+0=0$。
$N_P(2,5)=N_O(2,2)N_E(3,5)+N_O(2,3)N_E(4,5)+N_O(2,4)N_E(5,5)=1\cdot 1+0+0=1$。

長さ 5（全体）：$E\to EP$ について $k=1,2,3,4$ で和をとる。
$$N_E(1,5)=N_E(1,1)N_P(2,5)+N_E(1,2)N_P(3,5)+N_E(1,3)N_P(4,5)+N_E(1,4)N_P(5,5)$$
$$=1\cdot 1+0+1\cdot 1+0=2.$$

よって $w$ の導出木は $2$ 個である。これは $k=1$ の木（$x$ と $+(x+x)$ に分ける、すなわち $x+(x+x)$ に相当）と、$k=3$ の木（$x+x$ と $+x$ に分ける、すなわち $(x+x)+x$ に相当）の 2 通りに対応している。

答え：$2$

生成規則 $P\to OE$、$O\to +$ より、$P$ は $+E$ を導出する。したがって $E\to EP$ は実質 $E\to E+E$ であり、$E$ は $x$ と $+$ が交互に並ぶ文字列を導出する。

$w=x+x+x$ について、根の規則 $E\to EP$ で $w$ を $E$ が導出する前半と $P$ が導出する後半に分ける。$P$ は $+$ で始まるので、分け方は次の 2 通りである。

1. 前半が $x$、後半が $+x+x$ のとき。
$P\to OE$ で $O$ が $+$、$E$ が $x+x$ を導出する。$E$ が $x+x$ を導出する木は $E\to EP$ で $E\to x$、$P\to +x$ とするものだけなので 1 個である。
この場合の導出木は 1 個。

2. 前半が $x+x$、後半が $+x$ のとき。
前半を $E$ が導出する木は 1 個（上と同じ）。後半を $P$ が導出する木は $P\to OE$、$E\to x$ の 1 個。
この場合の導出木は 1 個。

前半が $x+x+x$ や空になる分け方は、$P$ が少なくとも 2 文字を導出するため不可能である。

合計 $1+1=2$ 個となる。これは $E\to E+E$ における 2 つの括弧づけ $(x+x)+x$ と $x+(x+x)$ に対応し、カタラン数 $C_2=2$ とも一致する。