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

方針　CYK 法の表に「その非終端記号から部分文字列を導く構文木の個数」を書き込む（数え上げ版 CYK）。

$w=w_1{w}_2\cdots w_8=abaabbab$ とし、部分文字列 $w_i\cdots w_j$ を $S$ から導く構文木の個数を $N(i,j)$ とする。

準備 1（$T,U$ の消去）　$T\to SB$, $U\to SA$ 以外に $T,U$ の規則はないので、$S\to AT\to aSb$, $S\to BU\to bSa$ と見てよい。また $A,B$ はそれぞれ $a,b$ だけを導く。よって $S$ の構文木は、規則
$$S\to ab\mid ba\mid SS\mid aSb\mid bSa$$
による構文木と 1 対 1 に対応する。

準備 2（$S$ が導く文字列）　どの規則も $a$ と $b$ を同数ずつ加えるので、$S$ が導く文字列は $a$ と $b$ の個数が等しい空でない文字列に限る。$p_k$ を $w_1\cdots w_k$ の（$a$ の個数）$-$（$b$ の個数）とすると
$$p_0,\dots ,p_8=0,1,0,1,2,1,0,1,0$$
であり、$p_{i-1}\ne p_j$ なら $N(i,j)=0$ である。特に長さが奇数なら $0$。

漸化式　長さ $2$ では $N(i,i+1)=1$（$ab$ または $ba$ のとき）。長さ $4$ 以上では、両端が $a\cdots b$ または $b\cdots a$ のときの「包む」規則と $S\to SS$ の分割を合わせて
$$N(i,j)=[\text{両端が }a\cdots b\text{ か }b\cdots a]N(i+1,j-1)+\sum _{k}N(i,k)N(k+1,j)$$
となる。和は $i\le k<j$ の範囲を動くが、$N\ne 0$ となるのは偶数長の部分だけである。

長さ 2　$N(1,2)=1(ab)$, $N(2,3)=1(ba)$, $N(4,5)=1(ab)$, $N(6,7)=1(ba)$, $N(7,8)=1(ab)$。$w_3{w}_4=aa$ と $w_5{w}_6=bb$ は $0$。

長さ 4
- $(2,5)=baab$：両端が $b\cdots b$ なので包む規則はない。分割は $N(2,3)N(4,5)=1$。よって $N(2,5)=1$。
- $(3,6)=aabb$：包む規則から $N(4,5)=1$。分割 $N(3,4)N(5,6)=0$。よって $N(3,6)=1$。
- $(4,7)=abba$：包む規則はない。分割 $N(4,5)N(6,7)=1$。よって $N(4,7)=1$。
- $(1,4)$, $(5,8)$ は $p_0\ne p_4$, $p_4\ne p_8$ より $0$。

長さ 6
- $(1,6)=abaabb$：包む規則から $N(2,5)=1$。分割は $N(1,2)N(3,6)=1$ と $N(1,4)N(5,6)=0$。よって $N(1,6)=2$。
- $(2,7)=baabba$：包む規則から $N(3,6)=1$。分割は $N(2,3)N(4,7)=1$ と $N(2,5)N(6,7)=1$。よって $N(2,7)=3$。
- $(3,8)=aabbab$：包む規則から $N(4,7)=1$。分割は $N(3,4)N(5,8)=0$ と $N(3,6)N(7,8)=1$。よって $N(3,8)=2$。

長さ 8　$(1,8)=abaabbab$ の両端は $a\cdots b$ なので
$$N(1,8)=N(2,7)+N(1,2)N(3,8)+N(1,4)N(5,8)+N(1,6)N(7,8)=3+2+0+2=7.$$

これを元の文法で確かめる。$S\to AT$ の場合は $T\to SB$ で $S$ が $w_2\cdots w_7$ を導くので $3$ 通りである。$S\to SS$ の場合は $2+0+2=4$ 通りである。$S\to BU$ は先頭が $b$ でないので使えず、$AB,BA$ は長さ $2$ の文字列にしか使えない。合計は $3+4=7$ で一致する。

よって構文木の個数は $\boxed{7}$ である。

この文法の言語は、規則 $S\to AB\mid BA\mid SS\mid aSb\mid bSa$ と同じ形になる。$AT$ は $ASB$、$BU$ は $BSA$ を表し、内側の $S$ は空でない。

$w=w_1\cdots w_8=abaabbab$ の部分文字列 $w_i\cdots w_j$ を $S$ から導出する構文木の個数を $f(i,j)$ とする。漸化式は次のとおり。
- 長さ 2 のとき、$ab$ または $ba$ なら $f=1$、それ以外は $0$。
- 長さ 4 以上のとき、$f(i,j)={\sum }_{k}f(i,k)f(k+1,j)$（$SS$ による分割）に、両端が異なる文字（$a\dots b$ または $b\dots a$）のとき $f(i+1,j-1)$ を加える。

長さ 2: $f(1,2)=f(2,3)=f(4,5)=f(6,7)=f(7,8)=1$。$f(3,4)=f(5,6)=0$。

長さ 4:
- $f(1,4)=0$（abaa は a と b の個数が等しくない）
- $f(2,5)$（baab）$=f(2,3)f(4,5)=1$（両端が同じ b なので包みなし）
- $f(3,6)$（aabb）$=f(3,4)f(5,6)+f(4,5)=0+1=1$
- $f(4,7)$（abba）$=f(4,5)f(6,7)=1$（両端が同じ a なので包みなし）
- $f(5,8)=0$（bbab は a と b の個数が等しくない）

長さ 6:
- $f(1,6)=f(1,2)f(3,6)+f(1,4)f(5,6)+f(2,5)=1+0+1=2$
- $f(2,7)=f(2,3)f(4,7)+f(2,5)f(6,7)+f(3,6)=1+1+1=3$
- $f(3,8)=f(3,4)f(5,8)+f(3,6)f(7,8)+f(4,7)=0+1+1=2$

長さ 8:
$f(1,8)=f(1,2)f(3,8)+f(1,4)f(5,8)+f(1,6)f(7,8)+f(2,7)=2+0+2+3=7$。

よって構文木の個数は 7。