文脈自由文法の導出と導出木

終端記号 $\{a,b,c\}$、非終端記号 $\{S\}$、開始記号 $S$ をもち、次の 3 つの生成規則からなる文脈自由文法 $G$ を考える。
$$S\to aSa,S\to bSb,S\to c$$
文字列 $abbcbba$ は $G$ で生成される。この文字列の $S$ からの導出に対応する導出木（構文木）を描いたとき、その頂点の個数を求めよ。ただし、頂点は根と葉を含めたすべての頂点（非終端記号のラベルをもつ頂点と終端記号のラベルをもつ頂点）を数える。

終端記号 $\{a,b,c\}$、非終端記号 $\{S,T\}$、開始記号 $S$ をもち、次の 4 つの生成規則からなる文脈自由文法 $G$ を考える。
$$S\to aSc,S\to T,T\to bT,T\to b$$
文字列 $w=aabbbcc$ は $G$ で生成される。開始記号 $S$ から $w$ を得る最左導出を書いたとき、生成規則を何回適用するか（導出のステップ数）を求めよ。

終端記号 $\{a,b\}$、非終端記号 $\{S\}$、開始記号 $S$ をもち、次の 3 つの生成規則からなる文脈自由文法 $G$ を考える。
$$S\to SS,S\to aSb,S\to ab$$
文字列
$$w=aabababbababab$$
（長さ $14$）について、$G$ における $w$ の導出木（構文木）の個数を求めよ。

終端記号 $\{a,b\}$、非終端記号 $\{S,A\}$、開始記号 $S$ をもち、次の 4 つの生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to SA,S\to AS,S\to b,A\to a$$
文字列 $w=aabaa$ について、$G$ における $w$ の構文木（導出木）の個数を求めよ。ここで、構文木の個数は $w$ の最左導出の個数に等しい。

非終端記号 $S$（開始記号）、終端記号 $a,b$ をもつ文脈自由文法 $G$ の生成規則を
$$S\to aS,S\to Sb,S\to \epsilon$$
の 3 つとする（$\epsilon$ は空列）。ここで $S$ から終端記号列 $w$ への導出とは、文形式の列 ${\alpha }_0=S\Rightarrow {\alpha }_1\Rightarrow \cdots \Rightarrow {\alpha }_k=w$（$k$ は正の整数）であって、各 ${\alpha }_{t-1}\Rightarrow {\alpha }_t$ が ${\alpha }_{t-1}$ の中の 1 つの $S$ を 1 つの生成規則の右辺で置き換えたものであるものをいう。2 つの導出は、文形式の列として異なるとき異なるものと数える。

$m,n$ を 0 以上の整数とする。$S$ から $a^m{b}^n$ への導出の個数がちょうど $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ であることを証明せよ。

終端記号 $\{a,b\}$、非終端記号 $\{S,T,A,B\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AB\mid AT\mid SB,T\to SB,A\to a,B\to b$$
長さ $8$ の文字列 $w=aaabbbbb$ について、$S$ を根とし葉を左から読むと $w$ になる $G$ の構文木（導出木）は何通りあるか。すなわち、$S$ から $w$ への最左導出の個数を求めよ。

終端記号 $\{a,b\}$、非終端記号 $\{S,T,U,A,B\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to AB\mid BA\mid SS\mid AT\mid BU,T\to SB,U\to SA,A\to a,B\to b$$
文字列 $w=abaabbab$（長さ $8$）について、$G$ における $w$ の相異なる構文木（導出木）の個数を求めよ。なお、これは $S$ から $w$ への相異なる最左導出の個数に等しい。

終端記号 $\{a\}$、非終端記号 $\{S,T\}$、開始記号 $S$ をもち、次の生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to SS\mid ST\mid a,T\to SS$$
文字列 $aaaaaa$（$a$ を $6$ 個並べた文字列 $a^6$）の、$G$ における最左導出の個数を求めよ。