社団法人
 電子情報通信学会

!"#$%& '信学技報'()'*'#&+

主辞情報付き文脈自由文法に基づく漸進的な依存構造解析アルゴリズム,,-,/. ,-,0,,1. ,-,0,
,
松原 茂樹
外山 勝彦
稲垣 康善
加藤 芳秀
2
名古屋大学大学院工学研究科 〒 34 35/64178 名古屋市千種区不老町
22名古屋大学情報連携基盤センター 〒 34 35/6417:9 名古屋市千種区不老町
222名古屋大学統合音響情報研究拠点 〒 34 35/64178 名古屋市千種区不老町;
5=<!>?@0ACBEDFGH?I?JKL <!>MHNOL MHFD><!>:L ?P>Q>R#?TSUV?P>Q>R?0W P#N?K'W P>QFD>5=NOW >X'W Y[Zあらまし

本稿では，依存関係情報を付与した文脈自由句構造文法に基づく漸進的な依存構造解析手法を提案する．

本手法では，範疇間の関係である到達可能性を用いて，文の入力と同時進行的に，修飾する単語と修飾される単語の間の関係である依存関係を計算する．本手法は，入力された文の断片を覆う構文木を必要としないため，構文木から依存関係を計算する手法に比べて，より効率的に依存関係を計算することができる．\^]_T` コーパスを用いた解析実験を行った結果，解析処理時間の短縮に，到達可能性を活用する本手法が有効であることを確認した．
キーワード

漸進的構文解析，依存関係，依存構造解析，到達可能性，漸進的解釈

a$bcedgfhdgfhigjlknmo*p ,rqts dgfhujv&fxwymo sgz|{ m|}$m ,-,-. ,-,0,Hq kn~'cegdgfv:bopa$m|wm ,0. ,0,-,Hq ~gi
a$~cebcedgfx|m$nm|kn ,
2 V
*



;
>JN>MHKX IFF@F PQ?PKeK ?PQ:L>QFD>$P?K GH?MrDLN F5=X IFL^I?RNG>5=RNOL>QFD>5=GHI?3:4 35/64 78$'>Z>P
2E2(




PF <!>MH?FPnOKX IPF@FQD^KeP#M[K L#>QFD>!P?K GH?M-D'LN F5=X IF:LO^I?RNG>5=RNOL>QFD>5=GHI?&34 35/6417:9'>Z>P
22E2
 (






^KeP#MHK F PMHKeQ >MHKeJnXFNGHMH?X PF <!>MH?FPn(KeGKe> X IOL>QFD>$P?K G?M-D'LN F5=X IF:L^I?RNG>5=RNOL
>QFD>5=GHI?34 35/64178$>Z>P;
5=<!>?@0ACBEDFGH?I?JKL <!>MHNOL MHFD><!>:L ?P>Q>R#?TSUV?P>Q>R?0W P#N?K'W P>QFD>5=NOW >X'W Y[Z¡$¢£1¤1¥¦#§¤]¨© ª¬«­«® ¯¬°#® ªr±1¯r©³²® ª¬­´!® µ¶±1©³®1´·"¸¶®1·-¨#¹°¹ºO©³´#± ¯r® ¸¶®1´·-­»°#® «® ´°#® ´±1¼$«­¯rªr© ´½²#­ª[® °!¹´«#¨¯r­ªr®ªr·r¯r¾#± ·r¾¯r®
½¯r­¸¶¸¶­¯C¿© ·r¨À·r¨®°#® «® ´°#® ´±1¼n¯r® » ­·r© ¹´ÁC]¨®Â¯r® ­±¨­²© »³© ·T¼Ã¯r®1»³­·r© ¹´Ä²® ·T¿Å® ® ´Äªr¼´·-­± ·r© ±± ­·-®1½¹¯r© ® ª© ªC¾#·-© » © Æ ® °ÀºÇ¹¯C±1¹´#È´® ±1·-© ´½­(¨® ­°¿É¹¯r°Â¿©³·r¨Â­(°#® «® ´°#® ´·^¿É¹¯r°Âªr© ¸¾#»³·r­´®1¹¾#ªr» ¼Á]¨#®¸¶® ·r¨¹°Â°¹®1ªO´#¹·^´®1® °Â·-¹± ¹´#ªr·r¯r¾± ·O·r¨®¿¨¹» ®"«­¯rªr®
·r¯r® ®C¹º­´!©³´#©³·r© ­»#º¯r­½¸¶® ´·Ê­´°·r¨¾ªÉ±1­´$²®(® Ë«®1± ·r® °!·-¹²®(ªr¾© ·r­²#»³®Vº¹¯"© ´± ¯r®1¸¶® ´·r­»ªr«¹Ì® ´*» ­´#½¾­½®C«¯r¹±1® ªrª[©³´#½Á\C´® Ë«®1¯r©³¸¶®1´·(¹´Í·r¨®\^]"_T`À± ¹¯r«¾#ª¨­ªªr¨¹E¿´Î¹¾¯·-®1±¨´© Ï¾#®*¹º"¾·r©³» © Æ © ´½·r¨®¯r® ­±¨­²© » ©³·0¼Ð·r¹n²®® Ñ® ± ·r© Ò®¶ºÇ¹¯¯r® °¾#± © ´½«¯r¹±1® ªrª[©³´#½¶·r©³¸¶®¹º·-¨#®Ó© ´± ¯r®1¸¶® ´·r­»°®1«®1´°®1´± ¼$«#­¯rªr© ´½ÁÔÃÕÖØ×Ù ¥Ú£© ´± ¯r®1¸¶® ´·r­»«­¯rªr© ´½Ê°#® «® ´°#® ´± ¼!¯r® » ­·r© ¹´Ê#°® «® ´#°® ´#± ¼$«­¯rªr© ´½Ê¯r® ­±¨#­²#©³» © ·T¼|¯r® » ­·r© ¹´Ê© ´± ¯[® ¸¶® ´·r­»:© ´È·r® ¯r«¯r® ·r­·r©³¹´
ÛÜ

まえがき

近年，自然言語処理の分野において，単語間の依存関係が注目を集めており，例えば，構文解析における曖昧性解消 ÝßÞ-à や
翻訳システムにおける訳文生成時の語順の決定 Ýßá-àãâÝßá-äà などに利用されている．
これまでに，依存構造解析に関する研究がいくつかなされているが Ýæå-àhâ[Ý çeàhâÝæè-à ，解析の漸進性の観点からはほとんど検討されていない．実時間音声対話 Ýßáeårà や同時通訳 Ýæé-à など，音声を聞きながらそれを同時に処理するシステムを検討するときには，漸進性の観点から依存構造解析を考える必要がある．
依存構造解析手法として広く知られるもののひとつに，文脈自由文法に基づく方法がある ÝæÞ-à ．この方法では，文脈自由文法の各文法規則に対して，範疇間の依存関係情報を付与することにより，構文木から単語間の依存構造を計算することができる．
しかし，この方法では，依存構造の計算に文全体に対する構文木を必要とする．そのような構文木を生成してから依存構造を計算すると，解析の漸進性が大きく損なわれることになる．
本稿では，依存関係情報を付与した文脈自由文法に基づいた
漸進的な依存構造解析手法を提案する．まず，文脈自由文法に

(a)



np(boy)det(the)vp*(saw)n*(boy)Theboyadv(yesterday)

vp1*(saw)v*(saw)det(the)then*(girl)
girl

dep
(b)

boy

図ê

saw

the

girl

yesterday

構文木からの依存構造計算例

ëßìí
構文木
ëßîí&ëßìí

から計算される依存構造

基づく漸進的構文解析と，構文木からの依存構造計算を組み合わせることにより，漸進的な依存構造解析が実現できることを示す．つぎに，これと同等かつ，より効率的な依存構造解析を実現する手法として，到達可能性に基づく漸進的依存構造解析
手法を提案する．本手法は，入力された文の断片に対する構文木を生成する必要がなく，効率的な解析が可能であり，漸進的な話し言葉処理に適している．提案手法の正当性を理論的に証明すると共に， ïðHññ!ò:óTðHðôgõ-ñöÝß÷-à に収録されている ø&òOùú
コーパスを用いた解析実験を行い，提案手法が解析処理時間の短縮に有効であることを確認した．直接的で素朴な方法（第 å章で述べる）に比べると，平均して約 á-äeäeä 分の á 程度の依存
構造解析時間の短縮を示した．
本稿の構成は以下の通りである．まず，次の第 å 章で，漸進的チャート解析に基づく依存構造解析手法について説明する．
第 Þ 章で，到達可能性に基づく漸進的依存構造解析手法を提案する．この手法の正当性を主張する定理 û の証明は付録に詳述する．第 ç 章では，実験の概要を述べ，その結果に基づいて提案手法の評価を述べる．

üÜ

図L

yesterday

np(girl)saw

The"!#%$&#(')(*,+-/.1032! #4")(*,+! '!
/576981:<; î>=@?
$(#A"$(# ê 'CB )($D;E$(# ê ' #&#F$/G ì@HB''$(# ê "$ !#I;J$ ! #%! #)($D ? 2G1.1281K ì@?

s(saw)

漸進的な依存構造解析

依存関係は，修飾する単語と修飾される単語との間の関係であるが，これは，句構造を定める文脈自由文法（ ýþgÿ ）の各文
法規則に句の間の依存関係情報を付与することにより，構文木から計算することができる ÝæÞ-à ．単語の出現順序に従って，漸進的に単語間の依存関係を計算するには，次の手続きを実行すればよい．
（ á ） 漸進的チャート解析のような， ýþOÿ ベースの漸進的構文解析手法により，入力文の断片に対する部分構文木を生成する．
（ å ） 文献 ÝæÞ-à の方法にしたがって，（１）により生成された部分構文木から単語間の依存関係を計算する．
本章では，まず，構文木から依存関係を計算する方法について説明し，次に，漸進的構文解析手法の一つである漸進的チャー
ト法，及びそれに基づく依存構造計算手法について述べる．

依存構造
依存関係では，修飾される単語は ðõ と呼ばれ，修飾する
単語は ð 'ðHñ ðHñ と呼ばれる．以下では，ðõ が  で ð ðHñðHñ が  であるような依存関係を  と書き，入力文中の単語間の依存関係の集合を，その文に対する依存構造と呼ぶことにする．図 á に依存構造の例を示す．

文法と辞書



構文木からの依存構造計算
文に対する依存構造は，ýþOÿ の各文法規則に対して ðõM  NPOQ と呼ばれる範疇を定めることにより，文に対する構文木から計算できる ÝßÞ-à ．各文法規則の右辺のただ一つの範疇が ðõM  NPOQ と呼ばれ，範疇が ðõ M NPOQ である句を，その他の句が修飾することを意味する．以下では，ðõ M  NQOP を記号 R で印付けることにする．例えば，図 å の文法において，文法規則 S
UTWVYX3V ' の ðõ M  NPOQ は X3V である．
各文法規則の ðõ M  NPOQ を定めることにより，構文木全体の意味を代表する単語である ðõ[Z]\eó^ が，次のように定義される．
［定義 á ］（構文木の ðõ_ZE\eó^ ） ` を構文木とする．
（ á ） `[aÝ Åàcb ならば，` の ðõdZ]\eó^ は である．
（ å ） `[aÝßÝfe@e e à bhg e e erÝfe7e@e à bJi e e erÝfe7e@e à b<j àck で，` の構成に用いられた文法規則 l"nmpoqe e@e1m  e e e1mdr の ðõ M  NPOQ が m 'である，すなわち，lsnmpoWe e e1m  e e e1m_r ならば，` の ðõ
Z]\eó^ は Ýfe7e@e à bJi の ðõdZ]\eó^ である．
t以下では，構文木 ` の ðõ-Z]\eó^ を uwv&x yWz`{ と書く．構文木の ðõ|ZE\eó^ が定まると，次に与える定義にもとづいて，構
文木から依存構造を計算できる．
［定義 å ］（構文木の依存構造） ` を構文木とする．関数 yv&V を
次のように定義する．
（ á ） `[aÝ Åàcb ならば，yv&Vz`JJa~} である．
（ å ） `~ayÝæÝQe@e e àbhgqe@e e[Ýfe e e àb i e@e e[Ýfe e e àb j à k とする．このとき，文法規則 lsm o e@e e1m-Je&e e1m r の ðõ M  NQOP が m- であ'る，すなわち，lm o e e e1m  e e e1m r ならば，yv&Vz`JhayWz`Jrz oy3v&VTÝfe7e@e àb<^である．ただし，yWz`J は次のように定義する．

yWz`han  uwv&x yTÝfe e e à bJi ^h auwv&x yWTÝQe e e à b ^=áa  a  -a u
tyv&Vz`J は ` から計算される依存構造である．図 á は構文木から依存構造を計算する例である．範疇の隣の括弧で囲まれた単語
は，その範疇を根とする構文木の ðõ|Z]\eó^ である．

漸進的チャート解析と依存構造計算
前節で述べた構文木からの依存構造計算を， ýþOÿ に基づく
漸進的構文解析により生成される部分構文木に対して適用する
ことにより，漸進的な依存構造解析を実現できる．本節では，
まず，漸進的に文の断片に対する部分構文木を生成する漸進的チャート解析について説明し，次に，漸進的チャート解析に基づいて依存構造を計算する方法について述べる．

漸進的チャート解析
漸進的チャート解析は，従来のチャート解析 ÝP-à と同様に，チャートと呼ばれるグラフ構造を用いて解析結果を保持する．
チャートは節点の集合，及び弧の集合から構成される．節点 ñ \ ð  は入力文中の単語と単語の間に位置し， 番目の単語と Wná 番目の単語  o の間の節点は，番号  でラベル付けされる．以下では，番号  でラベル付けされた節点を単に，節点 と呼ぶ．弧  ð  ð は，節点と節点を結び，入力文中でその弧が覆っている部分に対する構文木をラベルとしてもつ．この構
文木は項 fTðHó^- と呼ばれるデータ構造で表され，記法 Ý ¡à^b で¢ る．ここで，m は範疇であり，¡ は単語，記号 £ ある
表現されいは項のリストである． Ý ¡à^b という項 ` に対して，m を ` の範疇と呼ぶ． ÝQ£=àb のような項は未決定項 ¤ñ ð M NQð ¥=ðHó^- と呼ばれ，構造が決定されていないことを表す．項の中に出現する未決定項のうち，もっとも左に位置するものを最左未決定項と呼ぶ．弧にラベルとして付された項の中に未決定項が出現するとき，この弧を活性弧 Tõ M ^NP¦ðVð  eð  と呼び．そうでないとき，不活性弧 Nßñõ M ^NQ¦eðÅð  eð  と呼ぶ．
漸進的チャート解析は通常の上昇型チャート解析に新たな操作を導入した手法である．通常の上昇型チャート解析は，次のÞ つの操作を実行する．なお，以下では，チャートの節点  と節点  を結ぶラベルが ` である弧を z § `J と書く．
 操作 á 辞書引き  番目の単語 の範疇が m ならば，不活性弧 z¨Ðá    Ý àb をチャートに追加する．
 操作 å 文法規則の適用 不活性弧  1w Ýfe7e@e àb© がチャート中に張られているとき，文法規則 lsm¥ªe e e@« が存在するならば，弧  1w ÝßÝfe@e e à^bÝP£Tà¬|e e erÝQ£Tà^­Eà k  をチャートに追加する．
 操作 Þ 項の置き換え z  `J をチャート中の活性弧とし，`の最左未決定項を ÝQ£=àb とする．このとき，チャート中に不活性
弧  w@®> `¯§ が存在し，項 `¯ の範疇が m であるならば，` の最左未決定項を ` ¯ で置き換えた項をラベルとしてもつ弧をチャートの節点  と ® の間に追加する．
これに対して，漸進的チャート解析では，活性弧への文法規則の適用と活性弧による項の置き換えができるように，さらに次の å つの操作を導入している．
 操作 ç 活性弧への文法規則の適用 活性弧 z § `J がチャー
ト中に張られているとき，` の範疇が m であり，文法規則
lmdª°e e@e « が存在するならば，弧  1w Ý `ÝQ£Tàc¬Ie e e[ÝP£Tà­à k  をチャートに追加する．このとき，規則 ±Yal²mdªe e e&« を `に適用して得られる項を x VV3³µ´ z`  ±  を書くことにする．
 操作 è 活性弧の項による項置き換え  1w `J をチャート中の活性弧とし，` の最左未決定項を ÝP£Tà b とする．このとき，チャー
ト中に活性弧   ®  ` ¯  が存在し，項 ` ¯ の範疇が m であるなら
ば，` の最左未決定項を ` ¯ で置き換えた項をラベルとしてもつ
弧をチャートの節点  と ® の間に追加する．
すなわち，漸進的チャート解析は活性弧への文法規則の適用，及び，活性弧にラベル付けされた項の最左未決定項を別の活性弧にラベル付けされた項で置き換える操作を導入している．
例として，文の断片 ¶ò·ð\(¸d¹ õ^Z·º の解析を考える．通常の上昇型チャート解析では，次のような項が生成される．

ÝæÝßÝ » uwvà ,¼1½ Ý ¾@¿(´Eà1À à1À(ÁeÝQ£=àcÂÁ0àÃ

=á3ÝfSx ^à Â

=å3ÝæÝQSx Åà Â ÝQ£=à À(Á à ÂÁ(o=Þ3しかし， ¶ò·ðÄ\(¸I¹ õ^Z·º に対する項は生成されない．一方，漸進的チャート解析では，項 =Þ3 に文法規則 X3VÅ4X3VáÆx y3X を適用することにより，項ÝæÝßÝfSx Åà Â ÝQ£Tà À(Á à ÂÁwo ÝQ£=à^Ç  Â à ÂÁ³çW

を生成し， Tá の最左未決定項を項  ç で置き換えることにより， ¶ò·ð%\&¸È¹ õ^Z·º に対して項ÝæÝßÝ » uwvà,¼1½ÇÝ ¾@¿(´Eà À à À(Á ÝæÝßÝfSx Åà Â ÝQ£=à À(Á à ÂÁ(o ÝQ£=à^Ç@ Â à ÂÁ à Ãを生成する．

=è3

(a)np(boy)det(the)The(b)s(saw)
vp*(saw)n*(boy)boy

vp1*(saw)v*(saw)

adv(?)

dep
The

boy

saw

np(?)

saw

図É

文の断片に対する依存構造計算例



依存構造計算文の断片に対する依存構造は，漸進的チャート解析によって生成された項に，定義 å で定義した依存構造を計算する関数 yv&V
を適用することにより計算できる．例えば，項 Tè に含まれる項の ðõIZ]\eó^ は図 ÞTõ のように得られ，文の断片 ¶ò·ðÄ\(¸¹ õ^Zº に対する依存構造が，図 Þ にように計算できる．

ÊÅÜ

漸進的依存構造解析

前章で述べた手法により，漸進的に文の断片に対する依存構造を計算することができる．しかしながら，この方法は効率的ではなく，同じ依存構造をもつ項を多く作ってしまう可能性がある．例えば，漸進的チャート解析は ¶ò·ð\(¸d¹ õ^Z·º に対して式 Tè の項だけでなく，次のような項も生成するËÝæÝßÝ » uwvà ,¼1½ Ý ¾,¿w´Eà1À à1À(ÁeÝßÝæÝfSx"à1ÂÝQ£=àcÀ(Á-à1ÂÁ(o0ÝP£Tà§ÁÁ-àcÂÁTà^Ã^ÝæÝßÝ » uwvà,¼1½Ý ¾,¿w´Eà À à À(Á ÝßÝæÝfSx"à Â ÝQ£=à À(Á ÝP£Tà À(Á à ÂÁ(o ÝP£Tà^Ç@ Â à ÂÁ à ÃT÷ÝæÝßÝ » uwvà,¼1½Ý ¾,¿w´Eà À à À(Á ÝßÝæÝfSx"à Â ÝQ£=à À(Á ÝP£Tà À(Á à ÂÁ(o ÝP£Tà ÁÁ à ÂÁ à ÃTû項 Tè 〜 Tû からは，同じ依存構造が得られる．単に依存構造を求めることだけを考えると，このような同じ依存構造をもつ項をいくつも生成しないで，正しく依存構造が計算できるのであれば，その方が解析効率の観点から望ましい．同じ依存構造をもつ項を生成してしまう原因の一つとして，文法規則適用操作が挙げられる．すなわち，ある項に対する文法規則の適用の仕方が数通り存在したとしても，規則適用の結果得られる項の幾つかは同じ依存構造をもつ場合がある．漸進的チャート解析では，不活性弧のみならず活性弧に対しても文法規則を適用するため，その影響は大きい．そこで本章では，活性弧に対する文
法規則の適用に代わる操作として，到達可能性による項の結合操作を提案し，これによって漸進的に依存構造が計算できるこ
とを示す．

到達可能性
到達可能性は範疇間の関係であり，次のように定義される．
［定義 Þ ］（到達可能性） 文法規則 lÌm¥ªe e e « が存在する' を Í の反射推移閉包とする．
ならば，mÎÍÏl と書く．Í
'mÌÍª ならば，m が ª に到達可能  óTðõ M õ Oæð  であるといtう．
m が ª に到達可能であるとは，ª を根とする構文木が m を左端の子孫としてもつことが可能であることを意味する．
依存構造を計算するためには，構文木の ðõÈZ]\eó^ を定める必要があるが，文法規則を実際に適用することなく ðõdZ]\eó^を定めるために，本手法では，到達可能性を分類する．すなわ
ち，m が ª に到達可能であるということは，項 ÝQe,e e àb に対して幾つかの文法規則を適用すると，範疇が ª である項が得られることを意味するが，そのようにして得られた項の ðõdZ]\eó^ともとになった項 ÝQe7e e à b の ðõ-Z]\eó^ とがどのような関係にあるかという観点から分類する．なお，以下では，文法規則 ±の ðõ M NPOQ の位置を uwÐ3±  と書く．



［定義 ç ］ Í ，及び Í を範疇間の関係とし，次のように定義する．uwÐ3z± _a á である文法規則 ±ÑalÒÓm¥ªe e e@« が存d(saw)np(boy)(a)vp*(saw)&hv*(saw)det(the) n*(boy)
The

図Ô

結

合

項


Í l である． uwÐ3z±  ta  á である文法規則
在するならば，m Õ±alsmdª°e e@e « が存在するならば，m ÍUl である． t'm Íª は，左端の子孫の m の  ðõ-ZEe\ ó^ が ª に伝搬する
 '' Í
可能性があることを意味する．一方，mÍÍª は，m のðõdZ]e\ ó^ が ª に伝搬しない可能性があることを意味する．


到達可能性に基づく漸進的な依存構造解析
提案手法は，次の Þ つの手順からなる．
（手順 á ） 通常の上昇型チャート解析によって項を生成し，（手順 å ） 生成されたこれらの項を到達可能性を用いて結合し，（手順 Þ ） 結合された項から依存構造を計算する．
提案手法により，より効率的な漸進的依存構造解析が実現できる．もちろん，提案手法により生成される依存構造は， å 章で述べた手法のそれと等価であることが理論的に保証される．
上の手順 å において到達可能性により結合される項を結合項と呼ぶことにし，これを以下のように定義する．
［定義 è ］（結合項） ` za á ,Ö Ö Ö7 Th を通常の上昇型チャート
解析により生成される項とし，各  について ` の範疇を m ，`の最左未決定項の範疇を ª とする．× Ø wÙ   Ù   として，次の N1 と NPNc を満たすような並び `ho×|oWe e e1× Ú o1` × e e e§×À Ú oµ`Àを結合項という．

 'aÛÙÆ ならば，m f o Í ª ．
aÝÙ  ならば，m  oÍ ' 
Í Í ' ª ．

N14×
NPNcÜ×t

手順 å では，通常の上昇型チャート解析により生成された項を結合する．その操作は次の通りである．
 手順 åráÞz 1 `J をチャート中の活性弧とし，項 ` の最左未決定項を ÝP£Tà¬ とする．また，  ,®> ` o × o e&e e1× À Ú o ` À  をチャート中の結合項をラベルにもつ弧とし，` o の範疇を m とする．
このとき，mÍ 'ªならば，弧 z @®  `JÙÍ ' ÍÍ ' `ho×Doqe e e§×À Ú oµ`À
ª な ら ば ，弧を チャー ト に 追 加 す る ．mz  ®> `JÙÆ` o × o e e&e1× À Ú o ` À  をチャートに追加する．
例えば，項 Tá と Tå は図 ç のように結合される．ÙÆ は項が

 '

A

(b)

Y(w) ... Z(?)

Y(?) ... Z(?)

&h

&d

X(w)

saw

boy

A

' 

'

ÍÑÍ で結合関係 Íで結合されたことを，ÙÆ は項が関係 Íされたことを表す．
手順 Þ では結合項から依存構造を計算する．その計算を定義するために，まず結合項の ðõdZ]\eó^ を定義する．
［定義  ］（結合項の ðõdZ]\eó^ ） ß を結合項とする．
（ á ） ß が通常の上昇型チャート解析で生成される項ならば，
ß の ðõdZ]\eó^ は uwv&x yWß ．
a` o × o `<à1×Iàe e e1× À Ú o ` À（å ） ß
と し ，` o aÝßÝfe7e e àcbhge e e[ÝQe7e e àcbJá1â g ÝQ£=àbJá{e e e[ÝP£Tàb<jà k とする．このとき，
× o a°ÙÆ かつ，m-ã が ðõ M  NQOP ならば，ß の ðõ-Z]\eó^ は，`{à§×Iàe@e e1× À Ú o ` À の ðõ_Z]\eó^ である．そうでないとき，ß のðõdZ]\eó^ は uwv&x yW` o  である．
t以下では，結合項 ß の ðõdZ]\eó^ を uwv&x yWäJzß と書く．手順 Þ
では，結合項から次に与える定義にもとづいて依存構造を計算する．
［定義 ÷ ］（結合項の依存構造） ß を結合項とする．関数 yv&Väを次のように定義する．
（ á ） ß が通常の上昇型チャート解析により生成される項な

図å

到達可能性に基づく 032

X(w)ì K H= 81Kの伝搬

らば，yv&Vä{zßJayv&Vzß ．
a` o × o `<à1×Iàe e e1× À Ú o ` À（å ） ß
とし，` o ayÝæÝQe@e e àbhgqe@e e[Ýfe e e àbJá1â g ÝQ£=àbJáJe@e e[ÝQ£=àb j à k とする．このとき，

yv&VäJßYaæyqäJßÆyv&Väz`{à×IàWe e&e1× À Ú o ` À ã Ú oyv&VT ÝQe7e e àcb<^ oただし，yqäzß を以下のように定義する．また， uÈa²uwÐ3l/m o e e e1m r  とおく．
T õeáÜ× o aÛÙÆ で ua ® ならば，yqäJzßWaÑuwv&xyqä{z`{à1×Yàe e@e1× À Ú o ` À <
 auwv&x yW= Ýfe e e à b T áa  a -a~ u
TõeåÜ× o aÛÙÆ で u a  ® ならば，yqäJzßa  uwv&x yW=Ýfe e e à bJi J auwv&x yWTÝQe7e@e à b ^TáÆa  a 1Åa u §Åa  ® Úまたは Cauwv&x yWäJ`{à1×Iàe e e1× À o ` À Ü× o aÛÙÆ ならば，yqä{zßJayWz` o  ．
t '提案手法では，関係 Íを用いることにより，結合項中の項のðõ-Z]e\ ó^ を伝搬させる（図 èT õ ）．関係 Í ' ÍÍ ' が成り立 ðõ|ZEe\ ó^ は伝搬されない（図 è< ）．このようつ場合には，
に，到達可能性を活用することにより，活性弧に文法規則を適用することなく，文の断片に対する依存構造を漸進的に計算することができる．文法規則の適用の仕方が何通りもあるのに対して，分類した到達可能性の場合の数は高々 å 通りであるので，より効率的に依存構造を計算できる．さらに，提案手法が計算する依存構造は， å 章で述べた手法のそれと等価である．すな
わち次の定理が成り立つ．
［定理 û ］ ç を単語列とし，èWcç_ を漸進的チャート解析により生成された ç に対する項からなる集合とし， é%cç_ を ç に対する結合項からなる集合とする．このとき，yv7Vèq1ç_^êayv&Vä{é%cçÈ^ ．
t
証明は付録 á Ö に示す．

解 析 例
例として，文の断片 ¶òð\&¸d¹ õ^Zº の解析例を考える．この断片に対して，提案手法では，通常の上昇型チャート解析にしたがって，項 Tá と Tå を生成する． Tå の範疇は X で， Tá 'の最左未決定項の範疇は X3V であり，X Í
X3V であるので， Tá
と Tå は結合され，次の結合項を生成する．

ÝæÝæÝ » uvHà ¼1½ Ý ¾@¿(´EàcÀ/à1À(ÁeÝQ£=àcÂÁ0àÃ@Ù  ÝfSxÉàcÂTé

この結合項 =é3 の ðõdZ]\eó^ は，図  のように計算される．す
なわち，X

Í

 '

X3V を用いて，=å3 の ðõ|Z]\eó^ である ¶µ¹1õZº がîs(saw)

depC
det(the) n*(boy)
The

boy

í>ñ

&h

boy

saw

î7í>í>í

saw

î7í í

ì H= 81K
図 ëÒì 2 K
伝搬の例

î7í
î

図

英語文 

ò

î7í

ð


22K. = 0 ì 2·K36

ï

î7í

îï

î

ñ




入力単語数（単語） 28JG128 2K  に対して生成される弧ùñðHð d\Y:õ¦ðê NæññðHó·¹TðHó^¦eð  ÖÁTá-ä

に対して生成された弧の数を示したものである．生成された結合項をラベルにもつ弧の数は，漸進的チャート解析により生成された弧に比べて明らかに少ない．è 番目の単語 ¶µ NßññðHó^º が入力されたときを見ると，漸進的チャート解析では非常に多くの弧が生成されるのに対して，提案手法ではそれほど多くの弧は生成されていない．図 é は同じ文の解析処理時間を示したものであるが，実際， ¶µ NæññðHó^º が入力された段階での解析処理時間は大幅に短縮されている．

í íî

Á

í í>íîÁ

図断した．この結果は， 章の手法で解析を中断しなかった þ  文に対するもので文について解析を中断しなかった．

ï

22KY. = 0 ì 2EK36

ð




ñ


入力単語数（単語）28JGc28  2K 

に対する ê 単語当たりした．ýþOÿ ベースの漸進的構文解析に対して，構文木から依存関係を計算する手法を適用することにより，漸進的な依存構造解析ができることを示し，より効率的な漸進的依存構造解析を実現する方法として，範疇間の関係である到達可能性に基づく手法を提案した．到達可能性に基づく手法が，漸進的構文解析に基づく手法と同等の依存構造を生成できることを理論的に示し，解析処理時間の短縮に効果があることを実験により示した．
本手法は，同時通訳システム Ýßé-à における訳文生成 Ýæá-äeà に利用可能であり，効率的な翻訳の実現が期待できる．また，これまでに，依存関係を利用し漸進的構文解析を効率化する手法が提案されているが Ýæáeá-à ，この手法では部分構文木から依存構造を計算している．本稿で提案した依存構造計算法とこの手法を組み合わせることにより，漸進的構文解析の効率化が期待できるが，そのような手法についても今後検討したい．
文
献

@ì H
ì ì = ì=)( ììêÛì h:9G10 ? 6 !#ì "%$ ì  = 5 : 812=  K&ì "' = 5&: G)= ! * =22 148  3 6  5-K32,+->2  K32 .
.18  Gc: .16 0/ K32:9G G . :9: 2 . .16  G
 6 .12 G5+. ì .12032 ì K.18 ì  G1K ( . 281G56!879;:=< >@?BA;?BC9;DEA;FHG8CDEI>@CJ?BCKJ!;L = :  L7ë !
M =  !;--êÔ&å)N7ë2O ! L2O)O)O M $<8Q=2P R 28Q! ",2,- ì 8 ì .16 5EG ( 8 1æì 2 = 81K328 ì KêG ? . ì .16 812: ì .§6 = G
L2




. .

ì 8T6!H. UV 9KWYX;Z2?\[^6 ì K32,- 2 K32 ? 5&8 ì]TDE?\_V`DEA;?BCa92DbA2Fb7=92DcW




É2


Ô2

本稿では，単語間の依存関係を漸進的に計算する手法を提案（注 þ ）： þ 単語当たりの解析処理時間が ÿ を超えた文については，解析を中

英語文 

î

の解析処理時間びある．提案手法では，この þ 文を含む þ

章の手法
提案手法

í î

文の解析処理時間提案手法の解析効率を評価するための依存構造解析実験を行った．提案手法，及び å 章で述べた手法を ÷Næñ ¤ øïý （ ïðHñ ^NP¤ù=ùTùÉáeÿ]ùÄú ，メインメモリ áeÿô ）上に ÿEûÄü ý\Y\eñD÷NP¹ を用いて実装した． ïðHññ*òóTðHð õ-ñö"Ýß÷-à に収録されている構文木付
き ø&òOùú コーパス全 èe÷eû 文を対象とした．
提案手法と å 章で述べた手法の解析処理時間の比較を行った．図 ÷ は文の長さと一文あたりの平均解析処理時間の関係をg示している（注 ）．提案手法の一文あたりの平均解析処理時間はMä Ö äÞ¹Tð であるのに対して，å 章の手法のそれは åeÞ Ö ç'é¹Tð M であった．この結果からわかるように，到達可能性を用いた提案手法
は，漸進的な依存構造解析の解析処理時間の短縮に効果的である．
入力された文の断片を覆う弧の数は， å 章で述べた手法よりも提案手法の方が少なくなる．これによって解析処理時間が短縮されると考えられる．例えば，図 û は，英語文

む すïóÇªr® ±ô
解析処理時間î7í íTá の最左未決定項に伝搬する．結合項 Té に対して依存構造を求める関数 yv&Vä を適用することにより， ¶ ò· ð%\&¸I1¹ õZº の依存構造 » uwvI¾@¿(´q  ¾@¿(´dUSx Y^ が求められる．これは，
項 T è 〜 T û から得られる依存構造と同じものである．
ö"Ü
実験と結果の検討

ý"Ü

î

の数

文の長さ（単語）
図õ

章の手法
提案手法
依存構造の数

î7í>í í>íThe

v*(saw)

óÇªr®1±ô
7î 平均解析処理時間
í>í>í íïî í>í>í
章の手法
î7í>í
提案手法
î7í
î
í î
í íÁ îÁí í>íîÁí í>í>íî
Á
ï
ð
ñ

ï

î7í>í í>í>í

vp*(saw)

np(boy)

生成された弧の数

®



E.
/S/
9;Dd79;:=< >@?BA;?BC9;DEA;FYG8CDEI>@CaJ?BCKJ^A;DEegf;h;?B[jiDEDE>@Wlkm__?BCaDEIn9`c?\[;_oioJJ9KCA;?BCa92Dpc59;Vq79;:=<H>@?\A2?\C9;DEA;FbGrCaDEI>@CJ?\CKJ!-- ê7õcÔ2Nê5O !
s = .1812 ì : !rt ì ì K ì !2 ( 56
H Gc. êì ).1)6  Gc.16 ì :- ì 81G128 îì G12K = î 6 5&8 ìs 8uH=t = : :96 G)!
2



.

/
:92,(v 6 . ì :>K32w>- 2  K32 . 692GTE!rUV 9KWf`x ?B[yiDEDE>@Wrkm__?BCaDEI#9cl?B[;_zioJ{ìJ9KCA;?BC9;Dpc59;V=79;:=< >@?BA;?BC9;DEA;FGrCDbI>@CJ?BCaKJ!-- ê7Ô)Nê5ê !b"  . ì
t 8 (| !;}S"y!2u (   ê527ë u  s 8
~ 69G  28Q!  038122  2 H 3- 8 =îìî 69: 69G1.6 ./ = K32: G Q1 = 8ÄK32w>- 2  +
K32 . ? - ì 81Gc6  5H ì  2,v3- : = 8 ì .16 =  H!#UV9KWX;h2?\[]TDE?\_V`DEA;?BC9;DEA;F



å)

ë)


õ5






)



)

ê5O2

79;Dc5Wp9;D 7=92:=< >@?BA;?\C92DbA2FoGrCaDEI>@CJ?\CKJ!-- É7Ô)O2N7É&Ô,å !pt = - 2  +0 ì 572  !)]' 2 / ì 8 R ! ( 56 ê)7ë 
Ly * = / îì 81K =^ì  K *  * 2G / = !   ~ ì 81: 2 ? +. ? - 2J812 . = 5  6 | 28 1Q= 8
K32,- 2  K32 . ? 578 ì /S/ ì 8T6!UV 9KWlX;h2?\[g]TDE?\_V`DEA;?BCa92DbA2F79;Dc5W9;D
79;:=< >@?BA;?BCa92DEA;F GrCDbI>@CJ?BCaKJ!-- õL7É)N õcL) !Ht = - 2  0 ì 5&2  !]' 2  +
ì R (/ 8 !; 56 ê5)&ë s @ ì@? ! ]: 5 = 816 .10
G 032 ì . ìCì KDK ì . ì G1.18 ( . ( 812G·6 G ?  +ì. .16 3- 8 =  2GcG16 5)6/ !@. _K[;/ DECKA2F% _<@9;V`?7EG8{ . 2;{ X2;!g h 28 = v. .
.
 lpt!
ê5)2Os    s ì 8 ( G)!^$pn" ì . = 816 6 ì K s py s ì 8 6 R 692 H 6 | !
. .
(
ì . : ì 81572 ì =  . ì .12K  = 8T - ( G =)1 ~ 57:96 Gc0Y.1032  2  + $ 6 :9K36  5.
îì R 6!79;:=< >@?BA;?BCa92DEA;FgG8CDEI>@CJ?\CKJ!jL = :  ! M =  !
 8122ê5L-- Éê5O27
N É&É)O ! ê5)& É ( îì 8 ì !6";hG ì 6 !2 =@?ì ìÅì K^yì 5 ì)R 6 ! t 0 ì 81.T+" s ì .1G îì G12Km- ì 81Gc6 5 ì K.18 ì G 1 28E 6 6 / 812  2 . ì :G5 - =2R 2 : ì  5 ( ì 572 . / 
.18 ì  G1: ì .16 =  E!@UV9KW2x ?B[zlA;?\>@V A;FGbA;DEI>@A;I_lUV9K5_JJCaDEIoUA;KC YK (R 2.Q! 0 ì 6 : ì K!E
qC:EQ:=<9;JC>@:!Q-- å&Lê5&' 2 .  ê)>N å7L7Ô ! 0 õ ( îì 8 ì !) =@?ì ì¬ì KSì  ì2R 6! " s ì .1G 

/

 5
?
ì
( ì
=)( G
ì 036 26 .128T3- 812. ì .6 = î 2,+
 " . ;  8  GQ," 6 / :9.  2

H. 22 ~ 57:96 Gc0 ì Kyu ì - ì 2G12,6! M /  . =(=V ë ~ K í qie;A;DEK_5em@9`< {CKJoCDniV`?BC %KCA;FH]Db?B_FaF CI_DEK5_Eail]Q ¡;¡`¢2£YGb_K?\>V_¤l9;?\_#CDmiV`?BC Y{
KCA;FH]TDE?B_FF CaI_DEK_SX;Zx Z;!2-- êÉ7Ô)NêcÔ7É ! ê)) 

松原 茂樹，渡邊 善之，外山 勝彦，稲垣 康善，英日話し言葉翻訳
Mのための漸進的文生成手法，情処学自然言語処理研報， * + êcÉ&L ，-- 7!
 å)N ê5O2O ê5)2( ìì ( îì ì
ì =Cì
ì ì)R
êê¥  s ì 8 Gc2!" s ì .1G H 8 !6Sì  . ì  K¦Sì  5 6 ，. 812w+
2
.
p
:
r
t



§
1
8
1
G
6
5
6
1
.
¥
0
1
G
.
1
.
6
c
G
§
.
6
{
:
9
:
w
2
v
w
6
J
:
3
K
2,- 2  K32 . 6 2G)!
/ 

.
.
UV 9KWlh2?\[joA2?\>@V A;FqGbA;DEI>@A;I_nUV 9K_JJCDEI¦UA;KC YKgqC:¨EQ:{R ?7= ! M = <9;JC>@:!;-- É7å7É2N7É&å) !  =)w
L2O)Oê s  M ì)[R ì = ! M  s 6 ?ì20| ì2R 6!ouH
6 8 ì G ì@Hì !#q' = 03G ì)[R ì|ì  K
êcL2

ì
ì@Hì/îì . ì ! } K3281G1. ì K36 5 ( G125 2 .12K ( Gc28 ( .1.128 ì 2G
 w
 
 

/ 
E.
6  812 ì : +.16 / 2IG5- =)R 2  K36 ì : = 5 ( 2YG ? G1.12 / GT6!pUV 9KWf2Z;?B[diDEDE>@W
km_5_?BCDEI9cp?B[;_yilJJ9KCA2?\C9;Dnc59;V¤79;:=< >@?BA;?BCa92DEA;FYG8CDEI>@CJ?BCKJ!
-- L)O)O2N7L2O>õ !8t = :9: 2572  ì 8 R !}S"y!;u (   ê)) 

更に，è À を用いて，èWcçÈ を次のように定義する．
³

èWcç_<aÀ  ­è À cçÈtè À cçÈ は，ç に通常の上昇型チャート解析を施して生成される項に対して，  操作 ç ，  操作 è を T 回適用した結果得られる項の集合である．
提案手法により生成される，単語列 ç に対する結合項の集合 é%cçÈ は次のように定義できる．
［定義 á-ä ］（結合項の集合） 単語列に対して結合項の集合を返す関数 éhÀ を次のように定義する．
（ á ） 任意の単語列 ç に対して， éo@cçÈ<a®ªêcçÈ ．
（ å ） 任意の単語列 ç に対して，é  o cçÈaß¥w` o Ø ª%cç o   ß à Ø é 1ç|à&cç"a ç o ç|à7 が存在して ß は結合項` o ÙÆ@ß à または` o ÙÆß à である é%cçÈ を次のように定義する．
³

é%cç_<aÀ  oéJÀcçÈté À 1ç_ は T 個の項を結合して得られる結合項の集合である．

以下，定理 û の証明に必要な補題を順に証明する．
［補題 áeá ］ 任 意 の T に 対 し て ，` Ø è3À cç_ な ら ば，` ¯ Øè ¯ Á)²± ´71ç_hjªêcçÈ^  a Th ，及び文法規則 ±wÁzVÝa á 7Ö Ö Ö7« aT-¨   が存在し，`ax VV³µ´z` ¯  ± oqe@e e1±E¬& である．
証明 è3À cç_ の定義より明らか．
t［補題 áeå ］ ` Ø èW1ç_ とし，± o1± à e e e1±E¬ を « 個の文法規則の列とするとき，yv&Vzx VV³µ´z`  ± o e e&e1± ¬ hayv&Vz`J である．
付録
証明 « に関する帰納法により証明する．

定理 © の証明« anä のとき，xV3V³µ´` µ ha` であり，補題が成り立つのは明らか．
はじめに，証明に用いるいくつかの定義を与える．ªêcçÈ を通常の上昇型チャート解析により生成される，単語列 ç に対する項« a T のとき，補題が成り立つと仮定する．« a TdÀá とすを表す集合とする．̀ を項としたとき，Ð@x »@z`J で ` の範疇を表す． る．± o·alsmdªÑe e&e « ，¶%a± à e e e§±3À  o とおくと，ß¥a`Joc×Doe e e1×À Ú o1`À を結合項としたとき，Ð@x » ä zßJaÐ@x »@z`ho 
x VV3³µ´ z`  ± o ± àe e e± À  o とする．項 ` に対して文法規則 ±(Á zVÈa á ,Ö Ö Ö T«  を順に  操作
asxV3V³µ´=Ý `ÝQ£=à¬de e@e[ÝQ£=à­Eà k  ¶ øIeßáç に従って適用した結果得られる項を x VV³µ´z`  ±>oqe e e§±E¬& と書
く．このように表記するときには，暗黙の了解として，` に対である．このとき，して ± o â± à[â Ö Ö&Ö â ± ¬ が次々と適用できるものとする．項 ` の最左未決定項を項 ` ¯ で置き換えた結果得られる項を ±(v&Vz`  ` ¯  とyv&Vzx VV³µ´z`  ± o ± àe e e1± À  o ^書く．
a y3v&Vzx VV3³µ´ TÝ `ÝQ£=à¬de@e e[ÝQ£=à­Eà k  ¶ ^³øDe á(^
漸進的チャート解析により生成される，単語列 ç に対する項
a y3v&VTÝ `ÝQ£=à¬|e e e[ÝP£Tà­à k 
 帰納法の仮定 の集合 èW1ç_ は，次のように定義できる．
a y3v&Vz`h 定義 å［定義 é ］（漸進的チャート解析により生成される項） 単 語 列に対して項の集合を返す関数 è À を次のように定義する．
（ á ） 任意の単語列 ç に対して，è­ cç_<a®ª%cç_ ．
（ å ） 任意の単語列 ç に対して，è f o 1ç_EaÝèb¯ Á°Q± f o cç_èb¯ Á)²± f o cç_ ．ただし，èb¯ Á°Q± f o cç_ ，及び èE¯ ÁQ²± f o 1ç_ をそれぞれ次のように定義する．

èb¯ Á°)±  o cçÈa`7` ¯ Ø è cçÈ  及び文法規則 ± が存在して `ax VV³µ´z`¯  ±>è ¯ ÁQ²±  ocçÈa`7` o Ø êª 1ç o   `{à Ø è cç|à7^1ç"a ç o çDà&が存在し  `[a±(v7Vz` o  `{à@

以上から，帰納法により補題 áeå が証明された．
t［補題 áeÞ ］ ` Ø èWcç_ とし，± Á zVDaÍá @Ö Ö@Öw«  を uwÐ3z± Á <aá であるような文法規則とする．このとき，uwv&x yWx VV3³µ´ z`  ± o e e e1± ¬ ^ha
uwv&x yW`J である．
証明 « に関する帰納法で証明する．
« aÃä のとき補題が成り立つのは明らか．
« aT のとき補題が成り立つと仮定する．そこで，« aTDnáとする．±>oalsmdª°e e@e « ，¶êa± à e@e e1±3À  o とおく．このとき，  øIe á である．一方， uwÐ3z±o@<a á であるので，定義 á より，uwv&x yWTÝ `ÝQ£=à ¬ e e e[ÝP£Tà ­ àk<Jauwv&x yW`J
である．したがって， øIeßå

［補題 á ］ ` o Ø ªêcç o  ，かつ ` o の 最 左 未 決 定 項 を ÝP£TàbJáと す る ．ま た ，`{à Ø èWcç|à@ ，Ð@x »@z`Jà,saÓm-ã と す る ．そこ で ，`Òa±(v&Vz` o  `{à, と す る ．ま た ，ßà Ø é%1ç|à@ とし ，ß¥a` o ÙÆ@ß à を結合項とする．さらに，uwv&x yWz`<à@Ja~uwv&xyqä{zß à@ ，yv&Vz`{à7<ayv&Vä{zß à@ とする．このとき，

uwv&x yWzxV3V³µ´ z`  ± o1± à e e e1±À  o,^
a uwv&xyWzx VV³µ´=Ý `ÝQ£=à¬de e@e[ÝQ£=à­Eà k  ¶^ ^ øIe á(^a uwv&xyWT Ý &` ÝQ=£ à¬|e e [e ÝPT£ à­ à k 
 帰納法の仮定 a uwv&xyWz`J^ øIe å(^
以上から，帰納法により補題 áeÞ が証明された．
tØ
［補題 á-ç ］ `èW1ç_ と し ， uwv&xyWz`J a%£ と す る ．
±wÁzVaá ,Ö Ö Ö7«  を 文 法 規 則 と す る ．こ の と き ，
uwv&x yzx VV³µ´z`  ± oqe&e e1±¬ ^ha%£ である．
証明 « に関する帰納法により証明する．
« aÃä のとき，補題が成り立つのは明らか．
« aT のとき補題が成り立つと仮定する．« aT¥Àá とする．
± o al²m¥ªe e e « ，¶%a± àe&e e§± À  o とおく．
まず，xV3V³µ´`  ± o <aÝ `ÝQ£=à¬Ie&e e[ÝP£Tà­à k について，

uwv&x yWTÝ `ÝP£Tà¬Ie@e(erÝQ£Tà^­Eà k <aê£³øDe Þが成り立つことを， uwÐ3±oJaá のときとそうでないときに場合を分けて示す．
uwÐ3z±ohaÍá のとき：

uwv&x yWTÝ `ÝP£Tà ¬ e@e(erÝQ£Tà ­ àck<qauwv&x yz`JY 定義 áa£ 補題の仮定 

uwv&x yWTÝ `ÝP£Tà¬Ie@e(erÝQ£Tà¸_e e eÝP£Tà­à k 
a uwv&x yW= ÝQ=£ à`¸Ä  定義 áa£ 定義 áである．
以上より，  øIeßÞ( が成り立つ．
± o`¶%a± o1± à e e e1±À  o に対して，¶ の長さが T であり， øIeßÞ が成り立つことから，帰納法の仮定より，

³øDe çである．したがって，

uwv&x yWzxV3V³µ´ z`  ± o1± à e e e1±À  o,^
a uwv&x yWx VV3³µ´ TÝ `ÝP£Tà ¬ e e e[ÝP£Tà ­ àk  ¶^^ øIeßá&^a£^ øIe ç ^
以上から，帰納法により補題 á-ç が証明された．
t［補題 áeè ］ ` Ø èWcçÈ とし，±wÁzVpa á 7Ö@Ö Ö7T«  を文法規則とする．さらに，ある ± Tá a  a¹
 «  が存在して， uwÐ3z±  a  á とする．このとき，
uwv&x yzx VV³µ´z`  ± o e&e e1± ¬ ^ha%£ である．
証明 ` ¯ a°x VV3³µ´ z`  ± o e e e1± µÚ o  とおく．± aÝlUmdªÑe&e e «Mとする． uwÐ3z±  at á であるので，± の ðõ  NPOQ を · とすると，

uwv&x yWzxV3V³µ´ z`¯  ± ^
a_uwv&x yWT Ý ` ¯ ÝQ=£ à ¬ e e&e[ÝP£Tà ¸ e e e[ÝP£Tà ­ àckwTõ OP¸ の定義 
a_uwv&x yWT ÝPT£ à¸· 定義 áaÈ£ 定義 á
したがって，補題 á-ç より，である．
証明 `ho]aÝßÝfe@e e à bhg e e erÝfe7e@e à b

á1â g ÝPT£ à b á{e e re ÝQ£Tà b<j àck とおき，uIa
uwÐ3zl²nmpoe e e1m ã Ú om ã e e e1mdrÆ とおく．
まず，uwv&x yWz`JJaÛuwv&x y ä zß
を uIa ® のときと uのとき：

a  ® のときに場合分けして証明する．uIa ®

uwv&x yWz`Jauwv&x yWz`<à7
auwv&x yWäJzß à,
auwv&x yWäJzß 定義 á
 補題の仮定  定義 

u a  ® のとき：MuwÐ3z± o  aÍ á のとき：· を ± o の ðõ  NQOP とすると，

uwv&x yWzxV3V³µ´ TÝ `ÝP£Tà ¬ e e e[ÝP£Tà ­ àk  ¶w^Jaê£uwv&x yWz`JJaÛuwv&x yWäJzß かつ yv&Vz`Jhay3v&VäJzß

uwv&x yzx VV³µ´zxV3V³µ´z` ¯  ±   ±  oe@e e1±E¬&^Åaê£ で ある ．すな わ ち
uwv&x yzx VV³µ´z`  ± o e&e e1± Ú o ± ±  o e@e e1± ¬ ^êaê£ であり，補題 áeè がt
証明された．

uwv&x yWz`Jauwv&x yWTÝQe7e@e àb i auwv&x yWäJzß 定義 á 定義 

以上より， uwv&x yWz`{haÛuwv&x y ä ß である．
次に，yv&Vz`JDa yv7VWä{zß を証明する．そのためには，定義 å ，定 義 ÷ ，及 び 補 題 の 仮 定 yv&Vz`{à,aUyv&VäJß à@ から ，yWz`J_ayqäJzß を示せば十分である．ua ® と u a  ® の場
合に分けて証明する．
uDa ® のとき：

yWz`hauwv&x yW`{à7<w·auwv&x yWTÝQe e e àb<^T áÆa ·a   aÛ u  定義 åa  uwv&x y ä zß à J&  auwv&xyWT Ýfe e e à b< T á a  a   aÛ u  補題の仮定 a¥yqäJzß 定義 ÷u a  ® のとき：
yWz`ha  uwv&x yW=Ýfe e e à bJi JaÛuwv&x yW=Ýfe,e e àb<^^Tá a  a
    aÛ
 u   a ® または  auwv&x yWz` à  定義 åa  uwv&x yW= Ýfe e e à bJi JaÛuwv&x yW= Ýfe,e e àb<^^T á a  a    aÛ
 u   a ® または Cauwv&x yWäJß à@ 補題の仮定 a¥yqä{zß 定義 ÷
よって，yz`hJay ä zß となり，定義 å ，定義 ÷ ，及び補題の仮定により yv&Vz`Jhay3v&V ä zß である．
t以上から，補題 á は証明された．
［補題 áe÷ ］ ` o Ø ªê1ç o  ，かつ ` o の最左未決定項を ÝQ£=àbJá とする．また，`{à Ø èWcç|à ，Ð@x »@z`{à@Ea m¥ã とし，`a ±(v&Vz` o  `{à@
とする．また，ß à Ø é%cç|à@ とし，ßaÛ` o ÙÆß à を結合項とする．さらに，uwv&x yWz`<à7<aê£ ，yv&Vz`{à7<ay3v&VäJzß à, とする．このとき，uwv&x yWz`JJaÛuwv&x yWäJzß かつ yv&Vz`Jhay3v&VäJzßである．
証明 こ の 証 明 は ほ と ん ど 補 題 á の 証 明 と 並 行 に 進 められる．` o a ÝæÝfe@e@e àbhgqe e@e[Ýfe e e àbJá1â g ÝQ£TàcbJáJe e&e[ÝP£Tàb j à k とお き，uIauwÐ3zl²m o e e e1m¥ã Ú o m¥ã<e e e1m r  とおく．
まず，uwv&x yWz` à qauwv&x yz` ¯ à auwv&x yzß à,

 補題 áeÞ^ øIeß÷&^á よ り，yv&Vz`J a yv&V ä z`ho@Ù  ß à  ，
wu v&x yW`JhaÛuwv&x yWä{z` o ÙÆ@ß à@ である．また，Ð@x »@z`hJaÐ@x »@z` o haÐ@x » äJz` o ÙÆ@ß à@ である．
uwv&x yWz`{hauwv&x yWä{zß
ある ± Á T á a V ½a «  について， uwÐ3z± Á  a  á のときに は， '
'を uIa ® と u a  ® の場合に分けて証明する．
Ð@x »@z` ¯à |Í ÍÍm ，すなわち Ð@x » äJzß à,ÈÍ ' ÍÍ ' m であua ® の と き：uwv&x yWz`{ÝaÕuwv&x yW`{à@ aê£ ， uwv&x yWä{zßÝa
るので，定義 á-ä より `hoÙ  ß à Ø é%cçÈ である．補題 áeå より，uwv&x yTÝQ£=àbJá<a%£ である．
yv&Vz` à aÛy3v&Vz` ¯à  であるので，yv7V` à ©aÝyv&V ä zß à  である．
u a  ® のとき：uwv&x yWz`JJauwv&x yW=Ýfe e e àb i <a~uwv&xyqä{zß である． 他方，補題 áeè より，uwv&x yW` à Jaê£ である．したがって，補題 áe÷
以上より， uwv&x yWz`JJauwv&x yWä{zß である．
より，y3v&Vz`hasyv7V ä z`hoÙ  ß à  ， uwv&x yz`JDa4uwv&x y ä z`hoÙ  ß à 
次に，yv7V`hJayv&Vä{zß を証明するが，これは yW`hJayqäzß
である．さらに，Ð@x »@z`hJaÐ@x »@z`hohaÐ,x » ä z`hoÙ  ß à  である．
を示せば十分である．
 á のとき補題は成り立つ．すなわち，帰納以上から，TÅa³!
u[a ® のとき：yz`h ，y ä ß はともに } である． u a  ® のt法により補題 áeû が証明された．
とき：［補題 áeé ］ 任意の T ，及び単語列 ç に対して，ß Ø é À 1ç_ ならば，yv&Vz`JJayv&VäJß ，uwv&x yWz`{haÛuwv&x yWäJß かつ Ð@x »@z`JhayWz`Ja4CUuwv&x yWTÝQe e e àb i <
Ð@x » äJzß を満たす ` Ø èW1ç_ が存在する．
 aÛuwv&x yW=Ýfe e e à b< ^TáÆa ha    a u
証明 T に関する帰納法で証明する．
a"yz` o Ta á のとき，ß Ø éo1ç_<¾a ªêcçÈ a» èWcçÈ であるので，̀aßとおけば明らか．
a"y ä zßT a ³ のとき補題が 成り立つと仮 定する．ß Ø é ¼  o@1ç_
よって，yWz`h<ayqä{zß となり，yv&Vz`Jhay3v&VäJzß である．とすると，ある `ho Ø ªêcç_o@ ，ß à Ø é ¼ cç à _1ç aÌç_oç à  ，
以上より，補題 áe÷ が証明された．
t× Ø wÙ   Ù   が存在して，ßÝaæ`ho×©ß à とおける．帰納法の［補題 áeû ］ 任意の T と単語列 ç に対して，` Ø è3À cçÈ ならば， 仮定より，yv&Vz`{à,Yasy3v&VäJzß à,Iuwv&x yWz`<à@Ya uwv&x yWäJzß à, かつ
次の（１）と（２）を満たす ß Ø é%cç_ が存在する．
Ð@x »@z`{à@JaÐ@x »7ä{zß à@ を満たす `{à Ø èW1ç|à@ が存在する．
（ á ） yv&Vz`Jhayv7V ä zß ．
そこで，` o 最左未決定項の範疇を m とする．
 '（ å ） ` Ø è ¯ QÁ ²± ÀcçÈS
 ªêcçÈ のときには，Ð@x »@z`h<aÐ@x » ä zß×æaÛÙÆ のときには，Ð,x »7äzß à7 Ím であるので，文法規則
かつ uwv&x yWz`{hauwv&x y ä zß ．
±wÁ_aÛlÆÁdUªÁ7¡]Á&zVa á ,Ö Ö&Ö7T «  が存在して，ªhoa°Ð@x » ä zß à  ，
証明 T に関する帰納法により証明する．
ªÁêalÆÁ Ú oTá  V|ºa «  ，l¬am ，uwÐ3z±wÁ <a ázVDaÍá 7Ö@Ö Ö7T «  でTÃ
a ä のとき，` Ø è ­7cçÈ<ºa ª%cç_w a» é%1ç_ であり，ß¥a` とある（¡]Á は範疇の並びとする）．そこで，帰納法の仮定の ` à におけば補題が成り立つのは明らかである．
対して，` ¯ à ax VV³µ´z` à  ± oqe@e e1E± ¬  とおく．このとき，定義 é よT a ³ のとき補題が成り立つと仮定する．` Ø èE¼  o 1ç_ とすØ èW1ç à  である．Ð@x »@z` ¯ à ham であるので，±(v&Vz`Jo ` ¯ à 
¯
り，
`
à

è ¯ Á °Q± ¼  o cçÈ または ` Ø bè ¯ )Á ²± ¼  o cçÈ である．
ると，` Ø b
W
è
c

È
ç

`
が存在し，それはの要素である．これをとおくと，` Ø bè ¯ Á °)± ¼  o cç_ のときには，（１）の条件 yv&Vz`JEayv&Vä{zß を満たす ß Ø é%cçÈ が存在することを示せばよい．̀ Ø è ¯ Á °)± ¼  ocç_yv&Vz` ¯ à a-y3v&Vz` à   補題 áeå
であるから，文法規則 ± ，及び ` ¯ Ø è ¼ cçÈ が存在して，`aa-y3v&Vzß à   帰納法の仮定 x VV³µ´z` ¯  ±> である．補題 áeå より，yv7V`hêa°yv&Vz` ¯  である．
` ¯ Ø è ¼ cçÈ であるので，帰納法の仮定より，yv7V` ¯ hayv&V ä zß
uwv&x yWz` ¯à qauwv&x yz` à   補題 áeÞである ß Ø é%cç_ が存在し，yv&Vz`JaÛyv&Vz` ¯ ©aÝyv&V ä zß でauwv&x yzß à,  帰納法の仮定 ある．
` Ø Eè ¯ QÁ ²± ¼  o cçÈ のときには，` o Ø ªêcç o  ，`{à Ø Eè ¼z1ç|à&であるので，補題 á より，y3v&Vz`h]ayv7VWä{zß かつ uwv&x yz`JEa，ç aÝç o çDà である ` o â>`{à が存在して，`a ±(v&Vz` o  `{à@ であuwv&x yWä{zß である．さらに Ð,x » `hhaÐ,x » ` o JaÐ@x » äJzß である．
è ¼f1ç|à& であるので，補題 áeá より，` ¯à Ø bè ¯ QÁ ²± ´ cç|à@る．`<à Ø E×æaÛÙÆ のときには，Ð@x »7ä{zß à@qÍ ' Í Í ' m であるので，文法ªê1ç|à&  a ³ 及び文法規則 ± Á zV_a á @Ö@Ö Ö7T « a³¨   が存在し
規則 ±wÁêalÁªÁ,¡]ÁT áÆa V|ºa «  が存在して，ªJoEaÐ@x » ä zß¯c ，て，`{à·ax VV3³z´z` ¯ à  ± o e e e1± ¬  である．このとき，帰納法の仮定ªÁYaÝlÁ Ú oTá  V-¹a « Tâlm¬êa m であり，ある ±wÁTáIa V¥¹a « 
より，について， uwÐ3z±Á a  á である．` ¯ à a xV3V³µ´` à  ± oqe e@e1E± ¬& と
yv&Vz` ¯ à Jayv&Vä{zß à@³ øDe è
お く と ，` ¯ à Ø èWcç à  で あ る ．Ð@x »@z` ¯ à  aÞm で あ る の で ，±(v&Vz`Jo  ` ¯ à  は存在し，それは èW1ç_ の要素である．これを `Ð@x »@z` ¯à <aÐ,x »7ä{zß à@
³øDe9とおくと，補題 áeå と帰納法の仮定より，yv&Vz`¯ à êaÛyv&Vä{zß à@
uwv&x yWz` ¯ à Jauwv&x y ä ß à ³ øDe ÷であり，補題 áeè より， uwv&xyWz` ¯ à ha%£ であるので，補題 áe÷ より，
yv&Vz`J©aÝyv7VWä{zß かつ uwv&xyWz`JÄa/uwv&xyqä{zß である．さらにØである ß àé%cç à  が存在する．
Ð@x »@z`hJaÐ@x »@z` o <aÐ@x » äzß である．
そこで，`ho の最左未決定項の範疇を m とする．
 á のとき補題が成り立つ，すなわち，帰以上より，T a ® Ä
すべての ±wÁT á-a V a á のときには，a «  について uwÐ3z±wÁyt
納法により補題 áeé が証明された．
 ' 'Ð@x »@z` ¯ à  Ím である，すなわち， Ð,x »7äzß à@ Ím であるの補題 áeû より yv&VzèWcçÈ^ » yv&V ä é%cçÈ^ は明らか．
aで，定義 á-ä より ` o ÙÆ@ß à Ø é%1ç_ である．` o ÙÆ@ßà に対して，
補題 áeé より yv&VzèWcçÈ^w ¿ yv&V ä é%cçÈ^ は明らか．
a
したがって，これらから yv&VzèWcçÈ^ha y3v&V ä é%cçÈ^ である．
yv&Vz`{à@Wa¥yv&Vz` ¯ à   補題 áeå
すなわち，定理 û が証明された．
（定理 û の証明終り）a¥yv&Vzß à7 ^ øIße è
で あ る の で ，補 題