生成言語学をこっそり学ぶ（その４） - Finite Groups Fun 有限群あるいはちょこっと計算ファンの日記

第２節では、第１節の内容の形式化を行っています。今回は前半。

定義2.1〜2.3までの内容は解析木を表現するための簡約化されたラベル付きカッコ形式(labeled bracketing)の定義です。以降、解析木は簡約化されたwell-formedなラベル付きカッコ形式とします。カッコをとっぱらう演算 $d$ の定義は非終端記号も含めたものになっています。終端記号だけを引っ張り出す定義でいいような気もするのですが、後の都合のようです。また、非終端記号が直接でてこないラベル付きカッコ形式は terminalであると定義しています。

補題2.4は、 $d(\psi)$ を固定したときに、解析木 $\psi$ の長さ $|\psi|$ の制限を与えるもので、 $|\psi|\le 2|V_n|(2|d(\psi)|-1)+|d(\psi)|$ となります。ただし、この結果は第６節まで使いません。

定義2.5は補助的な定義で、well-formedとは限らないラベル付きカッコ形式 $\varphi$ に対して、内部(interior) $I(\varphi)$ 、左外部(left exterior) $E_l(\varphi)$ 、右外部(right exterior) $E_r(\varphi)$ を定義しています。
たとえば $\psi_3=[_{NP}[_Aflying]_A$ に対して、 $I(\psi_3)=[_Aflying]_A$ 、 $E_l(\psi_3)=[_{NP}$ 、 $E_r(\psi_3)=e$ となります。

定義2.6は前回予告していた標準分解(standard factorization)の定義です。分解される $\varphi$ は一般的に terminalかつ well-formedなラベル付きカッコ形式の部分列となっていますが、まあ、解析木の部分列としていいと思います。

定義2.6
well-formedなラベル付きカッコ形式の部分列でかつterminalである $\varphi$ のn項 $(n\ge 1)$ への標準分解とは、ラベル付きカッコ形式 $\psi_i\quad (i=1,\cdots,n)$ が存在して、
(i) $\varphi=\psi_1 \dots \psi_n$
(ii) 各々の $i$ について、 $\psi_i$ の一番左の記号は右カッコでなく、かつ一番右の記号は左カッコではない。

となります。定義上はfactor $\psi_i$ は空 e でもいいです。

次の定義2.7はかなり難解です。その後にある well-definednessについての説明もいまひとつなので、定義2.7に出てくるunique factorizationを実際に作るアルゴリズムを考えました。初期値の $\varphi$ は定義2.7にあるように一番左の記号は右カッコでなく、かつ一番右の記号は左カッコではないとします。

unique factorizationの作り方
$\varphi$ の左端から記号を取り込んでいって、一番左のfactorを作ることを考える。
(1) $\varphi$ が尽きたら終了。
(2) $\varphi$ の左端の記号が、
　(2A) 終端記号の場合、取りこんで(1)に戻る。
　(2B) 左カッコの場合、もし対応する右カッコが $\varphi$ の中にあれば、そこまでを取り込んで(1)に戻る。なければ(3)へ。
　(2C) 右カッコの場合、取り込んで(4)へ。
(3) すでに左カッコ以外の何かを取り込んでいれば終了（左カッコは取り込まない）。左カッコのみ取り込んでいる場合は、(2B)の左カッコを取り込んで(1)へ。
(4) $\varphi$ の左端の記号が、右カッコである限り取り込む。右カッコ以外が出てくると取り込まず終了。
これを繰り返すことで、factoringが得られる。

このようにしてできるfactorは内部(interior)を持っているのはほぼ明らかかと思います。また、(4)で出てくる右カッコは対応する左カッコがもともと $\varphi$ に入っていませんので、それを超えて終端記号を取り込むとそのfactorの内部(interior)が存在しなくなってしまいます。このため、それぞれのfactorは内部を持つためにはそれ以上右へ伸ばせないという意味で極大であると言え、定義2.7のunique factorizationの条件を満たしています。

定義2.7
$\varphi$ はwell-formedなラベル付きカッコ形式の部分列でかつterminalかつ一番左の記号は右カッコでなく、かつ一番右の記号は左カッコではない記号列とするとき、内容(contents) $C(\varphi)$ を上記 unique factorizationのfactorの内部(interior)の結合した記号列と定義する。また、 $R(\varphi)$ を $\varphi$ から $C(\varphi)$ を取り除いた残りと定義する。

例として挙がっている $\psi_2\psi_3=[_{VP}are [_{NP} [_{A} flying ]_{A}$ だと、unique factorizationは " $[_{VP}are$ "+" $[_{NP} [_{A} flying ]_{A}$ "なので $C(\psi_2\psi_3)=are [_{A} flying ]_{A}$ 。また、 $\psi_2\psi_3\psi_4=[_{VP}are [_{NP} [_{A} flying ]_{A} [_{N} planes ]_{N}]_{NP}]_{VP}]_{S}$ だと、" $[_{VP}are [_{NP} [_{A} flying ]_{A} [_{N} planes ]_{N}]_{NP}]_{VP}$ "+" $]_{S}$ "がunique factorizationで、 $R(\psi_2\psi_3\psi_4)=]_{S}$

ちなみに(14)の $\psi_4$ はミスプリで、最初の $[_{NP}$ は不要。p.58の中段やや下の例でも間違っています。ここは実は裏話があって、"they are flying planes" という文はAspectsにも似たような例文がある有名な多義文です。２つの意味とは、『彼ら（パイロットたち）は飛行機を飛ばしている』と『あれらは飛んでいる飛行機である』です。論文中の構文解析木(1)および(8)は無論、後者に対応し、(9)は前者に対応しています。ミスプリはこのあたり著者も混乱があったような…