数理解析研究所講究録
第 1649 巻 2009 年 31-38

31

拡張範疇文法の能力について
松原俊一
電気通信大学電気通信学研究科
情報工学専攻概要
本論文では,

機械翻訳のための形式的な文法モデルとして拡張範離文法を導入する. この文法は, 現在開発が進められている英和機械翻訳機で使われている文法モデルである. 近年の計算言語学では, tree adjoining
grammars と呼ばれる文法が, 自然言語の形式的な文法モデルとして注目され, 広く研究されている. 今回, 拡
張範疇文法が受理する言語のクラスと tree adjoining grammars が生成する言語のクラスの一致が示される.

1

序論

つれて構文の曖昧さが急速に増大する. この結果, 構
文解析で試される書換え規則の組合せが膨大となり,
近年の計算言語学では, 自然言語の形式化には, 文処理を破綻させる危険性が高まる. 二つめの問題は,
脈自由文法よりもやや強力な文法モデルが必要であ 構文木を構文解析以外の処理で利用しづらいことでるとされている [1][5]. 文脈自由文法の能力では, 自ある. 多くの非終端記号が無制限に使われ, 構文木
然言語の構文木を十分に扱えないからである. こう が複雑な形で表されるからである.
三つめの問題は,した中, 文脈自由文法よりもやや強力な生成能力を
自然言語の文法理論 $[7][15][17]$ との対応付けが難し持つ廿 ee adjoining grammars (TAGs と略す) [4] と呼いことである. これらの文法理論は, 具体的な構文のばれる文法モデルが注目されている. TAGs は, 自然情報源として必要である. ところが, TAGs では, 自言語の構文木を扱うのに十分な能力を持つことから, 然 語の文法理論における操作を明示的に扱うのがli:
自然言語処理に関連して多くの研究がなされている 難しい. 代表的なものに,
自然言語の文法理論におい$[1][5]$ . TAGs が生成する言語のクラスについては, 多て移動 $[7|[17]$ と呼ばれる基本操作がある.
項式時間の認識アルゴリズムや様々な代数的演算に一方, 自然言語の形式化において, TAGs 以外の注
関する閉包性など, 形式的な性質についても精力的
目すべき文法モデルに範疇文法 [6] がある. 範疇文法に研究されている $[8][11]$ . また, 自然言語の形式化
は, 各単語に対してその単語が構成する構文の情報をとして独立に導入された head grammars, 線形指標付持たせた文法モデルである. その情報は型と呼ばれ,文法, 組合せ範疇文法の三つの文法が, TAGs と等し構文の規則としても機能する. 各単語には, 型の有限い生成能力を持つことが知られている [10]. これは, 集合が割当てられる.
すなわち, 範疇文法では, 構文
TAGs による自然言語の形式化が妥当なことを示す結 の規則を各単語に割当て,
辞書に分散させることがで果の一つである. さらに, 文脈自由木文法 [9] の立場
きる. さらに, この特徴により, 構文木を単語だけでから TAGs を捉え直した spine grammars[2] と呼ばれ簡潔に表すことが可能である. 与えられた文の構文木
る文法モデルが, TAGs と生成能力を持つことが知らは, 割当てられた型の中から各単語一つずつ選ぶこれている. spine grammars の形式的な性質についてとで決定される. 選んだ型の列が妥当な構文木を表
は, 近年も [3] などの研究がなされている.
す場合, 二つの型を一つに書換える演算を繰返せば,
ところが, TAGs による自然言語の形式化には三つ
文全体を意味する型に書換えられる. ところが, 範躊の問題点がある. 一つめは, 構文解析の効率に関する文法の能力は, 文脈自由文法と同じことが知られてい問題である. TAGs の書換え規則では, 非終端記号がる [6]. よって, 自然言語を形式化するのに十分では無制限に使用され, 終端記号と明示的には結び付けらない.
れない. そのため, 単語特有の性質に依存する構文が本論文で導入する拡張範疇文法は, 範疇文法に対一般的な構文として扱われてしまう. 自然言語には, し,型の列の書換えを制御する新たな仕組みを加えた単語特有の性質が頻繁に現れるため, 文が長くなるに 文法モデルである.
この仕組みは, 自然言語の文法理32
論における移動を明示的に実現する. また拡張範疇文法は. 範疇文法の利点を保っているため, 構文の規則

定義 22

$A$

元,

$(.\hslash\cup\{e|)^{*}$

を各単語に割当て辞書に分散させることや, 構文木を
非終端記号を用いずに簡潔に表すことが可能である.
2 節で拡張範疇文法を導入し, 4 節においてその能力が線形指標付文法と等しいことを示す. したがって,[10] の結果により, 拡張範疇文法の能力が TAGs と一致することが分かる.

文字列とする.

を$\psi$

4 み規則)$\Sigma,e$$\Sigma$$\backslash fl$$\Sigma$を $G$ の素性値という.

は文標職と呼ばれる特別な原始型である.
は演算子と呼ばれる特別な三つの記号 と / と / を常に含む.
の型は,次で帰納的に定義される.
$S$

$G$

$G$

$*$

1. 原始型
2. 型$\Lambda$

に対し,$\alpha/A$

は型である.

$\alpha$

と原始型

$A$

に対し,

$\alpha/A$

は型である.

$\alpha$と原始型$\Lambda$

に対し,$\alpha*A$

は型である.

$\alpha$

と素性値

$e$

に対し,

$\alpha/e$

型着地#!R
擁性着地規(型転送 H J)$\Phi$の元,$w$$\Sigma\cup\{\epsilon|$

をは, 次の六つで$\vdash G$

ならば $(\psi,\gamma,aw)\vdash c(\psi,\gamma\alpha,w)$ .

$(\psi A,\gamma(\alpha/A),w)\vdash G(\psi,\gamma\alpha,w)$$\ovalbox{\tt\small REJECT}$

.

.

.

$(\psi,\gamma(\alpha*A),w)\vdash c(\psi A,\gamma\alpha,w)$の反射推移閉包を$\vdash G*$

たとき $G$ の還元とは,れる様相の列き,.

と$\beta_{0},\beta_{1},$

を単に

と表す.

$n$

を非負の整数とし$\beta_{0G}\vdash\beta_{|}\vdash c\cdots\vdash G\beta_{n}$$\cdots,\beta_{n}$

である.

$G$

と

と辞く.

$G$

$\mathcal{T}$$A_{0},$$\cdots,X_{n}$$\vdash_{G}$$\vdash$$\vdash$$1^{\cdot}$

$L$

$L$

.

.

.

$n\geq 1\rangle$$G$$G=(\ovalbox{\tt\small REJECT}, \Sigma,e, CAT,S)$$\ovalbox{\tt\small REJECT}=\{B,$$C,D,S,$ $T|$ ,$\Sigma=\{a,b,c,d|$ ,CAT$(a)=\{S/D/S*B,$ $S/D/T*B|$ ,$C\Lambda T(b)=\{T/C/T/B,$ $T/C/B|$ ,CA T$(c)=1C|,$$C\Lambda T(d)=\{D|$ ,$X_{n}A_{n}$

$G$

$e$

$\Sigma\cup\{\epsilon|^{1}$である. 以下に, 入力 aaabbbcccddd についての還元を示す.
( $e,$ , aabbccdd)$\epsilon$$\vdash$( $e,(S/D/S*B)$ , aabbbcccddd)$\vdash$( $eB,(S/D/S)$ , aabbbcccddd)$\Omega$$\Sigma\cup\{\epsilon|$が明らかなと$\{w\in\Sigma^{*}|(e, \epsilon, w)\vdash^{r}(e,S, \epsilon)|$$\Sigma$$\Sigma$$\cdots,A_{n}$

$A$

で実現さ

の受理する言上の言語として定義する.
上の言語 が拡張範離文法によって受理されるとき,は拡張範●醤語と呼ばれる.
$\vdash G$

語 $L(G)$ を$G$$\bigcup_{0\epsilon\Omega}CAT(a)$$\Sigma\cup\{\epsilon\}$$\vdash(eB,$$(S/D/S)(S/D/S*B)$ , abbbcccddd$)$$\vdash(eBB,(S/D/S)(S/D/S)$, abbbcccddd$)$$\vdash(eBB,(S/D/S)(S/D/S)(S/D/T*B)$ , bbbcccddd$)$

2.1 節では, これ以降.
は拡張範疇文法 $G=$
, CAT, ) を表すものとする.
$G$$(_{\iota}fl,\Sigma,e$$S$の元を $G$ の様相という.

$(ffl\cup\{e\})^{*}x\mathcal{T}^{*}x\Sigma$を様相とするとき,

$w$

を入力,

列と呼ぷ.

$\gamma$を還元列,$(\psi,\gamma,w)$$\psi$

を転送$\vdash(eBBB,$$(S/D/S)(S/D/S)(S/D/T),$ bbbcccddd$(S/D/S)(S/D/S)(S/D/T)(T/C/T/B)$ ,bbcccddd)$\vdash(eBBB,$$\vdash(eBB,(S/D/S)(S/D/S)(S/D/T)(T/C/T)$ ,bbcccddd)$\vdash(eB,(S/D/S)(S/D/S)(S/D/T)(T/C/T)$

1 本論文では. 空語を$\epsilon$

で表す.

の

上の

$\Sigma$を受理すを例として示す. この文法が受理する言語 $L(G)$ は, 文脈自由言語ではない言語として知られている.
とする. ただし,の型全体からなる集合を拶で表す. ただし,が明らかなとき, 戸を
で表す.
を原始型と
し,
を演算子としたとき, 薩 lA ..
で表される型をの基本型という. 言い換えると,基本型とは素性値 が現れない型である. CAT は,から基本型の有限集合の族への関数である. CAT は,の有限部分集合
に対して,
を集合
CAT
として定義することにより,のべき集合から基本型の有限集合の族への関数に拡張される.
$(\Omega)$を$F\oplus(\psi e,\gamma(\alpha/e),w)\vdash G(\psi,\gamma\alpha, w)$

は型である.

$G$$X_{1},$$a$$(E$ 還元規 $F|\rfloor)(\psi e,\gamma(\alpha/\Lambda)A, w)\vdash c(\psi e,\gamma\alpha,w)$

る拡張範疇文法

と原始型

4. 型

を

$\mathcal{T}^{\cdot}$

例 21 { $a,b,c$ , 朗上の言語 {♂bn♂♂ 1は型である.

$\alpha$

3. 型

5. 型

$A$

$\gamma$の元,$\mathcal{T}$の様相上の関係$G$$\alpha\in CAT(a)$$\Delta$$\vdash c$

定義 21 拡張範疇文法とは, 5 項組 $G=(fl,$,CAT, $S)$ のことである. ここで,とは空でない有限集合である. 1 の元を原始型,の元を終端記$e$の元,を擁性転送規則) $(\psi,\gamma(\alpha/\Lambda),w)\vdash G(\psi e,\gamma(\alpha/e/A),w)$ .

拡張範疇文法号という.

$\alpha$定義される.

$\Re$

2

を詔の元,

$(T/C/T)$ , bcccddd)

$)$

33
ように, 素性値$\vdash(eB,(S/D/S)(S/D/S)(S/D/T)(T/C/T)$に書換えられる. たが単独で還元列に現れることはないので, 型還元規則に柑当する規則はないことに注意する.
素性着地規則は, 転送列の右端に現れた を取り除き, 還元列の右端のをに書換える操作を表す. 型
は, 演算子 の右側のを切り離し, 転送列の右端に追加する型である.
したがって, 型転送規則 $(\psi,\gamma(\alpha*A),w)\vdash(\psi A,\gamma\alpha,w)$
は, 還元列の右端の型を に書換え, 転送列の右端に を追加する操作を表す. 型
は, 型$(T/C/T)(T/C/B)$ , cccddd)$\vdash(e,$だし, 素性値$(S/D/S)(S/D/S)(S/D/T)(T/C/T)$$(T/C/T)(T/C)$ , cccddd)$\vdash(e,$と対をなして$\alpha$$e$$(\psi e,\gamma(\alpha/e),w)\vdash(\psi,\gamma\alpha,w)$$(S/D/S)(S/D/S)(S/D/T)(T/C/T)$$e$$(T/C/T)(T/C)C$, ccddd)$\alpha/e$$\alpha*A$$\vdash(e,(S/D/S)(S/D/S)(S/D/T)(T/C/T)$$\alpha$$*$$A$$(T/C/T)T$ , ccddd)$\vdash(e,$$e$$(S/D/S)(S/D/S)(S/D/T)(T/C/T)$$\alpha*A$$(T/C)$ , ccddd)$\alpha$$A$$\alpha/A$$\alpha\parallel A$$\vdash^{*}(e,(S/D/S)(S/D/S)(S/D/T)(T/C)$, cdddに型着地規則の禁止という制限を加えた型であるとい$\vdash(e, (S/D/S)(S/D/S)(S/D/T)(T/C)C,ddd)$

える. 素性転送規則 $(\psi,\gamma(\alpha/A),w)\vdash(\psi e,\gamma(\alpha/e/A),w)$$\vdash(e,(S/D/S)(S/D/S)(S/D/T)T,ddd)$

は, 素性値$\vdash(e, (S/D/S)(S/D/S)(S/D),ddd)$

の型

$)$

を転送列の右端に加え, 還元列の右端$e$を $\alpha/e/A$ に書換える操作を表す. 追加されが取り除かれ, 還元列の右端の $\alpha/e/A$ が に書$\alpha/A$$\vdash(e.(S/D/S)(S/D/S)(S/D)D,dd)$

た$\vdash(e, (S/D/S)(S/D/S)S,dd)$

換えられるまで, 素性転送規則が使われる前の転送列は保存される. 転送列に追加された は, この $\alpha/e/A$$\vdash(e, (S/D/S)(S/D),dd)$$e$$\alpha$$e$とのみ対をなし, 素性転送規則によっ$\vdash^{r}(e,(S/D),d)$を書換えた$\vdash(e, (S/D)D, \epsilon)$て取り除かれる. このように, 還元列と転送列に現れ$\vdash(e,S, \epsilon)$

.

ここで,

た二つの

拡張範疇文法で用いられる各概念について直観的に説明する. 入力は, 左から順に処理されていく. 還元列と転送列は, 左端を底とするスタッ
クとみなされる. 素性値 は, 還元列と転送列を連
$e$

$e$

$\alpha/e$が呼応して還元を制御する.

拡張範疇文法で範疇文法に施した拡張の本質は, 転送列による還元の制御である. この制御は, 二つの演
算子 $J,$と素性値 を新たに用いて型を定義し, 型
$*$

$e$

着地規則, 素性着地規則, 型転送規則, 素性転送規則

動させるためのものである. 転送列上の は, 区切
記号の役割を果たしており,で区切られた原始型のの四つを新たに導入することで実現されている.

それぞれ独立したスタックとみなされる. 関
数 CAT は, 各終端記号と空語に有限個の許される型を定める. 転送列と素性値 は, 拡張範疇文法で3 線形指標付文法

$e$

$e$

列は,

$e$

新たに導入した概念である. 以下で, 定義 22 の各規則を順に取り上げる.
が終端記号のとき, 読込$a$

み規則を取り除き,$(\psi,\gamma,aw)\vdash(\psi,’\gamma\alpha,w)$

は, 入力の左端から$a$に許された型を還元列の右端に加える操作を表す.
が空語の場合, 読込み規則
は, 入力に依存せず, 空語に許された型 を還元列 の右端に加える操作を表す. 読込み規則以外の五つの規則は, 型が持つ演算子にしたがっている. 型還元規則
は, 型と原始型 を対とし. 還元列の右端に現れた $(\alpha/A)A$ を型に書換える操作を表す. 型着地規則$a$$\alpha$$\gamma$$a$$(\psi,\gamma,w)\vdash(\psi,\gamma\alpha,w)$$\alpha$$w$$\gamma$$(\psi e,\gamma(\alpha/A)A,w)\vdash(\psi e, \gamma\alpha,w)$

線形指標付文法は, 指標付文法 [6] の能力を制限した文法モデルであり, TAGs と等しい能力を持つことが知られている [10]. 線形指標付文法の非終端記号は指標を持つ.
を非終端記号,を指標の列としたとき, 指標付非終端記号はで表される. このとき,の左端がスタックの底であり, 右に向かって指標が積まれていく. スタックのトップが であるような非終端記号 をで表す.
を非終端記号の有限集合,
を指標の有限集合としたとき, 指標付非終端
記号全体からなる集合をで表す.
$\Lambda$$\eta$$A[\eta]$$\eta$$\eta$$A$$A[\circ\circ\eta]$$\Gamma$$I$$\Gamma[I^{r}]$$A$$\alpha/A$$\alpha$$(\psi A,\gamma(\alpha/A),w)\vdash\psi,\gamma\alpha,w)$

は, 還元列の右端に現れたと転送列の右端に現れた を対とし, 還元列の右
端を に書換え, 転送列の右端からを取り除く操作を表す 型は, 型の場合から類推される$a/A$$\Lambda$$A$$\alpha$$\alpha/e$$\alpha/A$

定義 31 線形指標付文法とは, 5 項組$(\Gamma,\Sigma,I. P,S)$ のことである.
とここで,$\Gamma$は有限集合である.
端記号,$\Gamma$の元を非終端記号,の元を指標と呼ぷ.
と $B$ を の元,と呼ばれる.
$I$$\Lambda$$\Gamma$$S$は$\zeta$$\Gamma$と$\Sigma$$G$$\Sigma$

$=$

と

$I$

の元を終

の元で開始記号$\zeta’$を$(\Gamma[\Gamma]\cup\Sigma)$

34
の元,

$\xi$

と

を

$\xi’$$I^{\cdot}$の元としたとき,$P$

4.

は次の形で表される書換え規則の有限集合である.
$L\Lambda[\circ\circ\xi]arrow\zeta B[\circ\circ\xi’]\zeta’$2.

$A[\xi]arrow\zeta$

上の関係

の元とし,

$\xi]arrow\zeta B[\circ\circ\xi’]\zeta’$

移閉包を

ただし,

を次で定義する.

$\Rightarrow G$を$\xi’’$$I^{\cdot}$$\zeta_{1}A[\xi]\zeta_{2}\Rightarrow_{G}\zeta_{1}\zeta\zeta_{2}$$\Rightarrow_{G}^{*}$と表す.

$r\iota$と$\zeta_{2}$。

$A[\xi]arrow\zeta$

である.

$\Rightarrow G$$\zeta_{0},$の反射推$\cdots,\zeta_{n}$$\xi_{0}\Rightarrow_{G}\zeta_{1}\Rightarrow c\cdots\Rightarrow_{G}\zeta_{n}$$\Rightarrow,$$\Rightarrow_{G}$として定義する.

$\Rightarrow^{*}$

上の言語 が線形指標
付文法によって生成されるとき,は線形指標付書語と呼ばれる.
例 31 {♂ $|n\geq 1|$ を生成す
涌上の言語 ♂
る線形指標付文法 $G=(\Gamma, \Sigma, I,P,S)$ を例として示す.
ただし,

.
.
.
.

$\Gamma=\ovalbox{\tt\small REJECT} S,$$T|$$\Gamma$の元,

1の元である.

TAGs の能力の一致を証明する.
次の補題は, 還元の前後で還元列の右端の型のみが変わる場合, 転送列がどう変化するかについての補題である. 具体的には, 転送列の最も右に現れる素性値$e$よりも左の部分が, この場合の還元の前後で保存されることを示している.

補題 4.1 拡張範疇文法 $G=(fl, \Sigma,e, P,S)$ が与えられ
たとする.

元.
$\{$

と $B$ と $C$ は$L$$\Sigma$$L$$a,$ $b,$ $c$$A$

この節では, 本論文の主定理である拡張範疇文法とを$\Sigma$$S[]\Rightarrow w|$の元,$\Sigma\cup\{\epsilon|$

4 拡張範疇文法の能力

が $P$ に属$\cdots,\zeta_{n}$$\Rightarrow G$

はを$A[\circ$

を $G$ の導出と言う. $G$ がで実現される列
明らかなとき,とをそれぞれと書
く. $G$ の生成する書語 $L(G)$ を 上の言語 $\{w\in\Sigma|$$\zeta_{0},\zeta_{1},$

$I$

$a$

$\zeta\iota A[\xi’’\xi|\zeta_{2}\Rightarrow G$

を非負の整数,の元としたとき.

$(\Gamma[\Gamma]\cup\Sigma)$$\zeta_{1}$の元としたとき,が $P$ に属すならば,である. また,$\zeta_{1}\zeta B[\xi’’\xi’]\zeta’\zeta_{2}$

すならば,

.

は

$(\Gamma[I^{*}]\cup\Sigma)^{*}$.

5. $A[0\circ\etaarrow B[\circ\circ]C[]$ .

.

$(\Gamma[l^{*}]\cup\Sigma)$$A[\circ\circ\etaarrow B[]C[\circ\circ]$$b^{n}f$,$\Sigma=|u,b,c,d\}$ ,$\gamma$を$\psi$$\tau*$と$\psi’$の元,を $(fl^{*}\{e\})^{r}$ の元,
と

を基本型,

$\eta$と$\eta’$

と

$v$

を刻 の
$*$

を

$\Sigma$

上の$(\psi\eta, \gamma\alpha, uv)\vdash*(\psi’\eta’,\gamma\alpha’, v)$

であ$\alpha$$\alpha’$$u$

文字列としたとき,
るならば $\psi’=\psi$ が成り立つ.

補題 4.1 は, 還元の長さに関する帰納法によって示されるが, 証明は本節の最後で行う.
次の定理 41 と定理 42 により, 拡張範疇文法と線形指標付文法の能力の一致を示す.

$1=\{1\}$ ,定理 41 任意の線形指標付文法$P=\{S[\circ\circ]arrow aS[\circ\circ l]d,$ $S[\circ\circ]arrow aT[\circ ol]d$$\tau[\circ\circ\etaarrow bT[\circ\circ]c,$ $T[\circ\circ\etaarrow bc|$,に対して. $L(G)=$,である. 例えば文字列 aabbccdd は, 次のように導出

される.
[l]cbb

$S[]\Rightarrow aS[I]b\Rightarrow aaT[lI]bb\Rightarrow aabT$$G$$L(G’)$ なる拡張範疇文法 $G’$ が存在する.

$\Rightarrow$aabbccbb.

線形指標付文法は定義 32 の標準形を持つ.

このこ(証明) この定理を証明するには, 標準形の線形指標付文法から拡張範疇文法を構成し, その線形指標付文法の生成する言語と構成した拡張範疇文法の受理する言語が一致することを示せばよい. このとき, 与えられる線形指標付文法について, 非終端記号の有限集持つことから容易に導かれる.

合と指標の有限集合が互いに素であると仮定しても一般性は失われない. このことは, どちらか一方の有定義 32 $G$ が標準形であるのは, 線形指標付文法 $G=$

限集合の元の名前を全て付け替えた文法が, 元の文法と同じ言語を生成することから明らかである.

とは. 線形指標付文法が [10] で導入された標準形を$(\Gamma, \Sigma, I, P,S)$の任意の書換え規則が, 次のいずれかの形で表されるときである.

1. $A[]arrow a$ .

が互いに素であるような標準形の線形指標付文法とする. この線形指標付文法$G$ から拡張範疇文法 $G’=$, CAT. $S)$ を構成する. ここで関数 CAT は.
から次のように構成される.
$G=(\Gamma, \Sigma, I, P, S)$を$\Gamma$と$I$$(\Gamma\cup I,\Sigma,e$

$P$

2.

$A[\circ\circ]arrow B\lfloor]C[\circ\circ\eta$.

3.

$A[0\circ]arrow B[\circ\circ\eta c[]$.

1. $A[]arrow a\in P$ ならば, $A\in CAT(a)$ .

35
2.

$A[\circ\circ]arrow B[]C[\circ\circ\eta\in P$$\in CAT(\epsilon)$

3.

$A[\circ\circ]arrow B[\circ\circ\eta C[]\in P$$\in CAT(\epsilon)$

ならば, $A/C*l/B$.

$I^{*}$

ならば, $A/C/B*l$$\Sigma^{r}$$A$$\Gamma$$\eta,$$(e\eta, \epsilon,w)\vdash*(e,\Lambda, \epsilon)$

であるならば, $A[\eta]\Rightarrow w$ である.

(b) の証明は, 還元の長さに関する帰納法による.

還元の長さが.

$0$のときは自明である. よって以下では, 長さ 1 以上の還元について考える.

この証明では, 帰納法の仮定を使うとき, 補題 4.1 が成り立つこ

5. $A[\circ\circ l]arrow B[\circ\circ]C[]\in P$ ならば, $A/C/B/l$$\in CAT(\epsilon)$$L(G’)$ が $L(G)$$)$に含まれることを示すには, 次の (b) を示せばよい.
の元(b)の元 $w,$の元に対して,4. $A[\circ\circ l]arrow B[]C[\circ\circ]\in P$ ならば, $A/C/l/B$$\in CAT(\epsilon)$の証明 補題 4.1 より,$(L(G’)\subseteq L(G)$.

とを用いる. 長さ 1 以上の (b) の還元では, 読込み規.

則が最初に適用されることに注意する. 最初に読込まの構成法から, A. $A/C*l/B,$ $A/C/B*l$
1 れる型は,は の元である.
$A/C/l/B,$ $A/C/B/l$ の五つの形に分けられる. ただし,とは の元である.
以下ではまず, $L(G)$ が $L(G’)$ に含まれることを示し, その後, $L(G’)$ が $L(G)$ に含まれることを示す.
型 を最初に読込む場合,で表さ(L(G) L(G’) の証明) 補題 4.1 より, $L(G)$ が $L(G’)$ れる. ここで,は$(a)$の元であり, CAT
はが CAT$(a)$ に属すので, CAT の構を元として含む.
に含まれることを示すには, 次の (a) を示せばよい.
(a)の元の元 $w,$の元をに対して, 成法から, $A[]arrow a$ が に属す. よって,
得る.
であるならば,
である.
ただし,

$A$

と $B$ と $C$ は$\Gamma$

の元,

$a$

は

$\Sigma\cup\{\epsilon|$

の元,

.

$P$

$I$

$B$

$C$

$\Gamma$$A$$(\epsilon, \epsilon,a)\vdash(\epsilon,\Lambda, \epsilon)$$\subset$

$a$

$A$

$\Sigma\cup\{\epsilon|$$A$$I^{*}$$\Sigma^{*}$$\eta,$$A[\eta]\Rightarrow^{s}w$

$P$

$A$

$\Gamma$(a) の証明は, 導出の長さに関する帰納法による.
導出の長さが のときは自明であるので, 以下で$0$は長さ 1 以上の導出について考える. この場合, 導出の最初に適用される書換え規則は, 線形指標付文法の標準形の定義から,$A[0\circ]arrow B[\circ\circ l]C[]$.

$A[]arrow a,$$A[\circ$$A[\circ\circ]arrow B[]C[\circ$ 。$t]$。$f]arrow B[]C[\circ\circ],$$\Gamma$,$A[0$ 。$\etaarrow$の五つの形に分けられる. ただし,と $C$の元,. 1 は の元,はの元である.

$B[\circ\circ]C[]$

は

$B$

$I$

$a$

$\Sigma\cup\{\epsilon\}$を最初に適用する場合,である. $A[]arrow a$ がの元であることから, 関数
CAT の構成法により,は CAT$(a)$ に属す. よって,が成り立つ.
書換え規則 $A[\circ\circ]arrow B[]C[\circ$ 。 を最初に適用す
る場合,
である.
書換え規則

$\Lambda[]arrow a$$A[]\Rightarrow a$$v$

は$\Sigma$$//e/B)B,$ $v)\vdash(e\eta e.\Lambda/C*l/e,v)\vdash(e\eta$,$A/C*l,$ $v)\vdash(e\eta l,A/C, v)\vdash^{*}(e,(A/C)C, \epsilon)\vdash(e,A$ ,$\epsilon)$で表される.

ある.

ここで,

と

$u$

$v$

は

$\Sigma$

また, 型 $A/C*l/B$ は CAT

上の文字列での元である.

$(\epsilon)$$A/C*lJB$ が CAT$(\epsilon)$に属すので, CAT の構成法からが得られる. $(e\eta e,A/C*$$A[\circ\circ]arrow B[]C[\circ\circ\eta\in P$$//e/B,uv)\vdash$$(e\eta e,(A/C*l/e/B)B,v)$であることから, 帰納法の仮定より $B[]\Rightarrow^{5}u$ を得る. 同様に,$(e\eta l,A/C, v)\vdash^{*}(e,(A/C)C, \epsilon)$$A[\eta]\Rightarrow B[]C[\eta l]\Rightarrow^{*}uC[\eta\eta\Rightarrow^{P}uv$と$(e\eta, \epsilon, uv)\vdash$

$A$

$I]$

$u$

型 $A/C*llB$ を最初に読込む場合,$(e\eta,A/C*lJB, uv)\vdash(e\eta e,A/C*l/e/B,uv)\vdash^{*}(e\eta e,(\Lambda/C*$$P$$(e, \epsilon,a)\vdash(e,\Lambda, \epsilon)$

ただし,$A[]\Rightarrow a$$(e\eta, \epsilon,w)\vdash r(e,A, \epsilon)$

上の文字列である.

$A[\circ\circ]arrow$

が $P$ の元なので, 関数 CAT の構成法か
ら型 $A/C*l/B$ が CAT
に属す.
であるこ

法の仮定より,$C[\eta\eta\Rightarrow^{*}v$$A[\eta]\Rightarrow B[]C[\eta l]\Rightarrow^{*}uv$

であることから, 帰納を得る. 以上によって,が成り立つ.

最初に読込まれる型が, $A/C/B*l,$$A/C/B/l$ の場合も各々同様にして示される.

$A/C/lJB$ ,ロ$B[]C[\circ\circ l]$$B[]\Rightarrow^{*}u$$(\epsilon)$とから, 帰納法の仮定より,れる. 同様に,の仮定より,$C[\eta l]\Rightarrow^{r}v$$(e, \epsilon.u)\vdash*(e, B, \epsilon)$が得らであることから, 帰納法を得る. 以上から,$(e\eta l,\epsilon,v)\vdash*(e,C, \epsilon)$$(e\eta, \epsilon, uv)\vdash(e\eta,A/C*l/B, uv)\vdash(e\eta e,A/C*l/e/B,uv)\vdash*$$(e\eta e,(\Lambda/C*l/e/B)B,v)\vdash(e\eta e,A/C*l/e, v)\vdash(e\eta,A/C*$$1,$$v)\vdash(e\eta l,\Lambda/C, v)\vdash*(e,(A/C)C, \epsilon)\vdash(e,A, \epsilon)$

最初に適用される書換え規則が, $A[$$l]C[],$$A[\circ\circ l]arrow B[]C[\circ\circ],$

を得る.

。
$\circ]arrow B[\circ$$A[\circ\circ\etaarrow B[\circ\circ]C[]$で表される場合もそれぞれ同様にして示される.

定理 42 任意の拡張範疇文法

た線形指標付文法の生成する言語が一致することを示す.

拡張範疇文法 $G=$
, CAT, $S)$ が与えられたと$G$する.
の基本型 に対し,を新しい記号とする.
$\alpha$の形に対して, $L(G)=$(証明) 以下では, 拡張範疇文法から線形指標付文法を構成し, その拡張範疇文法の受理する言語と構成し$(\mathcal{A},$。

$G$$L(G’)$ なる線形指標付文法 $G’$ が存在する.

$\Sigma,e$$\langle\alpha\rangle$

この $G$ から線形指標付文法 $G’=(\Gamma\cup fl,\Sigma, fl, P,S)$を構成する. ここで,$(\{/, /, *\}fl)$の元$\beta$が存在して,

36
が CAT$\alpha\beta$

る集合を
元

$\}$

に含まれるような基本型$(\Sigma)$で表したとき,$\Phi$$\Gamma$は集合$\alpha$

次に (C2) について示す.

全体からな
は

$\{\langle\alpha\rangle|\alpha$の$\Phi$

である.

拡張範疇文法の定義から, CATの任意の元が基$(\{/,/,*\}fl)^{r}$
本型であることと, 原始型 と
の元 に
対して.
が基本型を表すことに注意する. 書換え
規則の集合 は, 次で構成される.

この場合, 次の (el) が成り立つことを用いる.
(el) 還元列に現れる基本型に対して,$\alpha$$\langle\alpha\rangle$

が$\Gamma$に$(\Sigma)$に$(\Sigma)$$A$$A\beta$$P$$1A\beta\in CAT(a)$ならば.

$2\langle A\rangle\in\Gamma$

3 a/孟$\rangle\in\Gamma$

ならば,$4\langle\alpha\prime A\rangle\in\Gamma$

ならば,$\langle$$5\langle\alpha*A\rangle\in\Gamma$$q\alpha/A\rangle\in\Gamma$$A[\circ\circ]arrow a\langle A\beta\rangle[\circ\circ]\in P$$\langle A\rangle[]arrow\epsilon\in P$

ならば,

.

$\langle a’\Lambda\rangle[\circ\circ]arrow A[]\langle\alpha\rangle[\circ\circ]\in P$.

$\gamma/B,$$\epsilon,$

図の元,$\gamma$

本型,

は ({/, L }」刃) の元である.

$\beta$

は疏の元,

$a$

は

$\Sigma\cup\{\epsilon|$の元,$\alpha$

まず,

以下では,

$L(G)$ が $L(G’)$.

$\langle A\rangle$.

がは $G$ の基に含まれることをの証明 補題 4.1 より.
$)$

ばよい.
$A$

, 灰

の元

$(e\eta, \epsilon,w)\vdash^{*}(e,A, \epsilon)$$\Sigma^{*}$$\eta,$の元 $w$ に対して,であるならば $A[n]\Rightarrow^{*}W$ で$\Gamma$$(e,A, \epsilon)$の元$\Lambda,$$([/,$ $/,$ $*$$\}$凋 y の元 , 凋 の元$\beta$元 $w$ に対して,$(e\eta,\Lambda\beta.w)\vdash(e,A, \epsilon)$

ば

である.

$\langle A\beta\rangle[\eta]\Rightarrow w$$\Sigma^{*}$$\eta,$のであるなら(cl) と (c2) の証明を, 還元の長さに関する帰納法
によって同時に行う. この証明では, 帰納法の仮定を使うとき, 補題 41 が成り立つことを用いる.
まず, (Cl) について示す. この場合, 還元の長さがであるならば自明であるから, 以下では, 長さ 1 以
上の場合を考える. 長さ 1 以上の還元は,$(e\eta,A\beta, w)\vdash(e.A, w)$ で表される. ここで,はは CAT$(a)$ の元である. 型の元であり, 型
が CAT$(a)$ に属すので,の構成法から $A[oo]arrow$$0$$\Sigma\cup\{\epsilon|$$A\beta$が $P$ の元である.

$(e\eta,A\beta, w)\vdash(e,A, w)$

ることから, (c2) の帰納法の仮定より,を得る. 以上によって,
られる.

$B$

は

$(e, B, \epsilon)\vdash*(e,B, \epsilon)$

での元である.

$)*$の構成法から,$P$$\langle A\rangle[]\Rightarrow\epsilon$$\langle A\rangle[]arrow\epsilon$がが得られる.

で表される. ただし,

$B\sqrt{}$

ので,

す.

の元

$u$

と

は

$v$

$\Sigma$$a$はの構成法から,$B\gamma’$$(e,\Lambda\gamma, v)\vdash(e,A, \epsilon)$$\sqrt{}$はが CAT$(a)$ に属す$B[\circ\circ]arrow a\langle B\gamma’\rangle[\circ\circ]$$(e\eta,\langle A\gamma/B)(B\sqrt{}),uv)\vdash*(e, (A\gamma/B)B, v)$

納法の仮定より,の元,

上の文字列である. また,は CAT$(a)$ の元である. 型$P$$\Sigma\cup\{\epsilon|$

が $P$ に属であること$\langle B\sqrt{}\rangle[\eta|\Rightarrow u$を得る.

であることから, (C2) の帰が得られる. 以上により,$\langle A\gamma\rangle[]\Rightarrow v$$\langle A\gamma/B\rangle[\eta]\Rightarrow B[\eta]\langle A\gamma\rangle[]\Rightarrow a\langle B\gamma’\rangle[\eta]\langle\Lambda\gamma\rangle[]\Rightarrow^{*}auv$

が成り立っ. 次に, 型着地規則を最初に使うとき, (C2)の還元は $(e\eta B,A\gamma/B,w)\vdash(e\eta,A\gamma,w)\vdash^{n}(e,A, \epsilon)$ で表される. (el) により.の構成法から,す.

$\langle\Lambda\gamma/B\rangle$$\gamma/B,$に属すので,$\gamma*B$.

$\gamma/e$$P$

が $P$ に属であることから, (C2) の帰.

$\langle A\gamma\rangle[\eta]\Rightarrow w$$\langle A\gamma/B\rangle[\eta B]\Rightarrow\langle A\gamma\rangle[\eta]\Rightarrow$が$\Gamma$$(A\gamma/B\rangle[\circ\circ B]arrow\langle A\gamma\rangle[\circ\circ]$$(e\eta,A\gamma,w)\vdash*(e,A, \epsilon)$

納法の仮定より.
$\beta$は$w$を得る. 以上より,が成り立っ.

の場合もそれぞれ同様にして示される.

$\Lambda\beta$$P$$a\langle A\beta\rangle[\circ\circ]$である. ただし,の場合, (C2) の還元は, 最初に適用さ$(\eta.\epsilon,aw)\vdash$$a$中は図の元である. (el) により,に属すので,$(\{/, /, *\}fl)$

同様に,$\Gamma$$\gamma*B$

から, (C2) の帰納法の仮定より,

ある.
(c2)

$\Lambda\beta$のれる規則が読込み規則であるか型着地規則であるかによって, さらに場合分けされる. まず, 最初に適用されるのが読込み規則のとき, $(e\eta,A\gamma/B.auv)\vdash$

型の元$\Gamma$$\Gamma$$(e\eta,(A\gamma/B)(B\gamma’),uv)\vdash(e, (A\gamma/B)B, v)\vdash(e,\Lambda\gamma, v)\vdash*$$L(G)$ が $L(G’)$に含まれることを示すには, 次の (Cl) と (c2) を示せ

(cl)

図

$B$

に属す. よって,$P$$L(G’)$ が $L(G)$ に含まれることを示す.

$(L(G)\subseteq L(G’)$$*\}$

表される. ただし,$*$示し, 次に,$\gamma/B,$$\gamma/e,$は $([/,$ $/,$$\beta=\gamma/B$
$A$

が CAT

が存在するので,$\beta$の場合, (C2) の還元は,$\beta=\epsilon$$\langle a*A\rangle[\circ\circ]arrow\langle\alpha\rangle[\circ\circ A]\in P$

ただし,$\alpha\beta$の形によって五つに場合分けされる. 五つの形$\beta$とは,.

$\langle\alpha/A\rangle[\circ\circ A]arrow\langle\alpha\rangle[\circ\circ]\in P$に対して,$\alpha$

属すような $([/, /, *\}fl)$ の元の$\langle\alpha/A\rangle[\circ\circ]arrow A[\circ\circ]\langle\alpha\rangle[]\in P$

ならば,還元列に現れる基本型

定義から, (el) が直ちに導かれる.
(C2) の還元は, 最初の還元列を成している型

.

ならば,

属す.

$\beta$であ$\langle A\beta\rangle[\eta]\Rightarrow w$$A[\eta]\Rightarrow a\langle A\beta\rangle[\eta]\Rightarrow^{r}aw$

が得$(L(G’)\subseteq L(G)$の証明 補題 41 より,$)$$L(G’)$ が $L(G)$に含まれることを示すには, 次の (dl) と (d2) を示せ
ばよい.
(dl) fl の元$\Lambda,$$A[\eta]\Rightarrow w$$t\hslash$.

の元$\eta$.

$\Sigma$の元 $w$ に対して,であるならば $(e\eta,\epsilon,w)\vdash(e,A, \epsilon)$ で

37
ある.

本節の残りで, 補題 41 の証明を行う.
(
補題 4.1 の証明) 証明は, 還元の長さに関する帰納(d2) 図の元 $A,$の元の元法による. 還元の長さが のときは明らかである. 長の元に対して,であるならばさ 1 以上の還元は, 最初に適用される規則によって場$(e\eta,A\beta, w)\vdash*(e,A,\epsilon)$ である.
合分けされる. ただし. 型還元規則を最初に適用する(dl) と (d2) の証明は, 導出の長さに関する帰納法 還元は, 補題 41 の前提の形で表されない. したがっによって同時に行われる.
て, 型還元規則以外の五つの規則の場合について (fl)まず, (dl) を示す. 導出の最初に適用される書換え から (f5) で述べる. 証明中の以下では,
は図の元,
規則は
は
の元,
で表されるものに限られる.
の三つは基本型,,$(\{/, 1, *\}\mathcal{A})^{r}$$fl^{*}$$\beta,$$\Sigma^{*}$$\eta,$$0$$w$$\langle A\beta\rangle[\eta]\Rightarrow^{t}w$$A$$\Lambda[0\circ]arrow a\langle A\gamma)[o\circ]$

ただし,

$a$

は

$\Sigma$の元,って (dl) の導出は,る.

は $(\{/, /, *\}fl)^{s}$ の元である. よ$\gamma$$A[\eta]\Rightarrow a\langle A\gamma\rangle[\eta]\Rightarrow^{*}aw$$A[\circ\circ]arrow a\langle A\gamma\rangle[\circ\circ]$

ら, 型

$a$

$\alpha l,$$\alpha_{2},$$\psi_{2},$

で表され

例

$*$

$\psi_{3}$$\alpha_{3}$の三つは (図 {e}) の元,
$*$

の元,

は

$\gamma$$\gamma*$

$*$

の元,

$u,$

$\eta_{1},$

$w$

$v,$

$\eta_{2}$$\psi_{1}$.

$\eta_{3}$

の三つは

の三っは
$\Sigma$

上の文

字列をそれぞれ表す.

が $P$ の元なので, $P$ の構成法かが CAT$(a)$ に属す.

$\Sigma\cup\{\epsilon|$(fl) 読込み規則が最初に適用されるとき,であることから, (d2) の帰納法の仮定より, $(e\eta,A\gamma,w)\vdash(e,A, \epsilon)$$\gamma(\alpha_{1}/A),auvw)\vdash(\psi_{l}\eta_{1},\gamma(\alpha_{1}/A)\alpha_{3},uvw)\vdash\wedge(\psi_{2}\eta_{2}$が得られる. 以上から,$\gamma(\alpha_{1}/A)A,vw)\vdash(\psi_{2}\eta_{2},\gamma\alpha_{1}, vw)\vdash*(\psi_{3}\eta_{3},\gamma\alpha_{2\prime}w)$$A\gamma$$(e,A, \epsilon)$$\langle A\gamma\rangle[\eta]\Rightarrow^{*}w$(d2) の導出で最初に適用される書換え規則は $P$ の$\langle A\rangle[]arrow\epsilon,$$\langle A\gamma/B\rangle[\circ\circ]arrow B[\circ\circ]\langle A\gamma\rangle[]$$\langle A\gamma lB\rangle[\circ\circ]arrow B[]\langle A\gamma\rangle[\circ\circ]$$\gamma$は,$(\{/, /, *\}\mathcal{A})^{r}$

書換え規則
の導出は,

$\langle A\gamma*B\rangle[$,$\circ]arrow\langle A\gamma\rangle[0$ 。
。
$B]$の仮定より,,

が基本型ならばる.

を最初に適用するとき, (d2)で表される. このとき,$(e,A, \epsilon)\vdash n$が成立するのは明らかである.
1 鴬負え規則を最初に適 ffi
する場合, (d2) の導出は$uv$ で表される.
ただし,とは上の文字列である.
であることから, (dl) の帰納法の仮定より,
が得られる. 同様$(e\eta, \epsilon, u)\vdash’(e, B, \epsilon)$に,であることから,が得られる. 以上から l$\psi_{2}=\psi_{3}$型転送規則が最初に適用されるとき,

(f2)

,

$\gamma\alpha_{2},$で表される.

$v)$

本型の定義から,$\Sigma$$B[\eta]\Rightarrow^{*}u$は基本型であ$\alpha_{1}$$(\psi_{1}\eta_{1},\gamma(\alpha\downarrow*A), uv)\vdash(\psi_{1}\eta_{I}A,\gamma\alpha_{1},uv)\vdash*(\psi_{2}\eta_{2}$$\langle A\gamma/B\rangle[\eta]\Rightarrow B[\eta]\langle A\gamma\rangle[]\Rightarrow*$$v$$\alpha_{1}/A$である.

$\psi_{3}=\psi_{1}$$\langle A\gamma/B\rangle[\circ 0]arrow B[\circ\circ]\langle A\gamma\rangle[]$$u$も基本型なので$\alpha_{1}$$(\psi_{2\eta_{2},\gamma\alpha_{1},vw)\vdash}\cdot(\psi_{3\eta_{3},\gamma\alpha_{2},w})$

帰納法の仮定より,$(e,A, \epsilon)$

であることから, 帰納法を得る. 基本型の定義から,$\psi_{2}=\psi_{1}$の五つの形に分けられる.

$\langle A\rangle[]arrow\epsilon$$\langle A\rangle[]\Rightarrow\epsilon$,$(\psi_{1\eta_{1},\gamma(\alpha_{1}/\Lambda)\alpha_{3}}$$\alpha_{3}$$uvw)\vdash*(\psi_{2\eta_{2},\gamma(\alpha_{1}}/A)A,$ $vw)$の元である.

$\langle A\gamma/B\rangle[\circ\circ B]arrow\langle A\gamma\rangle[\circ\circ]$

ただし

.

,

で表
される. 拡張範躊文法の定義から, CAT $(a)$ の元であるは基本型である. よって,,$(e\eta, \epsilon,aw)\vdash(e\eta,A\gamma,w)\vdash^{r}$が成り立っ.

構成法から,$(\psi_{1}\eta_{1}$が基本型なので, 基も基本型である. よって,$\alpha_{1}*A$$\alpha_{1}$$(\psi_{1\eta_{1}\Lambda,\gamma\alpha_{1},uv)\vdash}*(\psi_{2\eta_{2},\gamma\alpha_{2},v})$

納 法の仮定より,$|||$$\psi_{2}=\psi_{1}$であることから, 帰を得る.

であることから, (d2) の帰納法の仮定より, $(e,A\gamma, v)\vdash*(e,A, \epsilon)$ を得る. 以上から,(f3) 素性転送規則が最初に適用されるとき, 還元
は, $(\psi_{1}\eta_{1}, \gamma(\alpha_{1}/\Lambda),auvw)\vdash(\psi_{1}\eta_{1}e, \gamma(\alpha_{1}/e/A),auvw)\vdash$$(e\eta,A\gamma/B,uv)\vdash(e,(A\gamma/B)B, v)\vdash(e,A\gamma,v)\vdash^{\alpha}(e,A, \epsilon)$$(\psi_{1}\eta_{I}e,\gamma(\alpha_{1}/e/A)\alpha_{3}, uvw)\vdash*(\psi_{2}\eta_{2}e,$ $\gamma(\alpha_{1}/e/A)A$が成り立っ.

$vw)$$\langle A\gamma\rangle[]\Rightarrow^{*}v$

最初に適用される書換え規則が,$B[]\langle A\gamma\rangle[0\circ],$$\langle A\gamma*B\rangle[\circ$$B]arrow\langle A\gamma\rangle[\circ\circ]$

される.

$\langle A\gamma/B\rangle[\circ\circ]arrow$$]arrow\langle A\gamma\rangle[\circ\circ B],$。

$\langle A\gamma/B\rangle[\circ$。

の三つの場合もそれぞれ同様にして示

ロ

線形指標付言語のクラスは, TAGs が生成する言語のクラスに一致することが知られている [10]. したがって, 定理 41 と定理 42 から直ちに次の定理を
得る.

$|$

$(.-.-. , (\alpha_{1}/e), ..)$($(\psi_{3\eta_{3},\gamma\alpha_{2},w})$,$(\psi_{2}\eta_{2},\gamma\alpha_{1}, vw)$$\vdash$で表される. ただし,$\alpha_{-}$$\vdash^{r}$は. ,の元である. 拡張範疇文法の定義から, CAT $(a)$ の.

$\overline{\pi}$は基本型なので,$\alpha_{3}$は基本型である. よって,$(\psi_{1}\eta_{1}e,\gamma(\alpha_{1}/e/A)\alpha_{3}, uvw)\vdash^{*}(\psi_{2} .2e,\gamma(\alpha_{1}/e/\Lambda)A,vw)$$1$であることから, 帰納法の仮定より,

:
を得る
.
$E$
$d$

ので,
て,
$|5$
$!$

$(\mathcal{A}\cup\{e\})^{r}$

に現れる

ことから
$1$

定理 43 拡張範疇言語のクラスは, TAGs が生成する
言語のクラスと一致する.

$\vdash$

$e$

の元である

は, それぞれ$\psi_{2}=\psi_{1}$$\psi_{2}$$\psi_{2}\eta_{2}$とである. また,

基本型の定義から,$\alpha_{1}$$\psi_{1}$$\psi_{3}=\psi_{2}$$\psi\downarrow\eta_{1}$の最もの右端であるが基本型なも基本型である. よっ$\alpha_{1}/\Lambda$

であることから,を得る. 以上によって,$(\psi_{2\eta_{2},\gamma\alpha_{1},vw})\vdash(\psi_{3\eta_{3},\gamma\alpha_{2},w})$

納法の定義より,$\psi_{2}\eta_{2}=\psi_{1}\eta_{1}$と38$\psi_{3}=\psi_{1}$が得られる.

(f4) 型着地規則が最初に使われるとき,$\gamma(\alpha_{1}/A),$$(\psi_{1}\eta_{1}A$$uv)\vdash(\psi_{1}\eta_{1} , \gamma\alpha_{1}, uv)\vdash(\psi_{2}\eta_{2},\gamma\alpha_{2}, v)$

A. K. Joshi and Y. Schabes, “Tree-adjoining grammars”, in Handbook of Formal Languages, ed. G.
Rozenberg and A. Salomaa, pp.69-124, SpringerVerlag, Berlin, 1997.

[6]

B. Partee, A. Meulen, and R. Wall, Mathematicalmethods in linguistics, Kluwer academic publishers, Dordrecht, 1987.

[7]

A. Radford, Syntactic theory and the sbucture ofEnglish: A minimalist approach, Cambridge uni-

,

で表され

が基本型なので, 基本型の定義から,本型である. よって,る.

[5]$\alpha_{1}/A$$\alpha_{1}$も基$(\psi_{1}\eta_{1}, \gamma\alpha_{1}, vw)\vdash(\psi_{2\eta_{2},\gamma\alpha_{2},w})$

であることから, 帰納法の仮定より,れる.

$\psi_{2}=\psi_{1}$が得ら(f5) 素性着地規則が最初に使われる場合は, (f4) で示した型着地規則が最初に適用される場合と同様にして示される.

口

versity press, Cambridge, United Kingdom, 1997.

5

[8]

むすび

S. Rajasekaran, ‘Tree-adjoining language parsingtime”, SIAM J. Comput., vol.25, no.4,
inpp.862-873, 1996.
$O(n^{6})$

本論文では, 自然言語の新たな形式化として拡張範疇文法を導入し, その能力が AGs と等しいことを示した. 一方で, 任意の拡張範疇言語をが空集$\Gamma$$CAT(\epsilon)$

合の拡張範疇文法によって受理できるかどうかという未解決の問題が残されている. 構文の規則を全て単語に割当て, 辞書に完全に分散させた場合, CATは空集合となるため, この問題を解くことは, 自然言$(\epsilon)$

語の形式的な言語のクラスを決定するうえで重要で
ある.

参考文献
[1]

[2]

[3]

[4]

A. Abeille and O. Rambow, Tree adjoining grammar:An overview”, in Tree adjoining grammars:
Formalisms, linguistic analysis and processing, ed.
A. Abeille and O. Rambow, pp. 1-68, CSLI publications, Stanford, Califomia, 2000.

[9]

W.C. Rounds, ”Mappings and grammars on trees”,
Mathematical Systems Theory, vol.4, no.3, pp.257287, 1970.

[10] K. Vijay-Shanker, D.J. Weir, “The equivalence offour extensions of context-free grammars”, Mathematical Systems Theory, vol.27, no.6, pp.511-546,

1994.
[11] D.J. Weir, ”A geometric hierachy beyond context-

fiee languages”, Theoretical Computer Science,
vol. 104, pp.235-261, 1992.
[13] 川原田郁夫, 笠井琢美, “転送スタック付きプッ

シュダウンオートマトンと Linear indexed grammar について”, 信学論 (D-I), vol J84-D-I, no. 12,
pp. 1583-1590, Dec. 2000.

A. Fujiyoshi and T. Kasai, Spinal-formed contextfree tree grammars”, Theory of Computing Systems, vo133, pp.59-83, 2000.

[15] 久野すすむ, 高見健一, 英語の構文とその意味一A. Fujiyoshi, ‘Application of the CKY Algorithm
to recognition of tree structures for linear, monadic
context-free tree grammars”, IEICE Trans. $Inf$. &Syst. vol.E90-D, no.2, pp.388-394, 2007.

[17] 立石浩一, 小泉政利, 文の構造 (英語学モノグラ

A.K. Joshi, L.S. Levy, and M. Takahashi, “Tree adjunct grammars”, J.Comput.Syst.Sci, vol.10, no. 1,

pp. 136-163, 1975.

生成文法と機能的構文論 (開拓社叢書 16), 開
拓社, 東京, 2007.
フシリーズ 3) , 原口庄輔, 中島平三, 中村捷, 河
上誓作 (編), 研究社, 東京, 2001.