第１章　演習問題解答例

演習１  演習２  演習３  演習４  演習５  演習６  演習７  演習８　演習９ 演習１０

 

演習１　ここでは2文節の文を示す．

(1)    　先生は行く

(2)    　先生は行った

(3)    　先生が行く

(4)    　先生が行った

(5)    　先生を行く

(6)    　先生を行った

(7)    　先生で行く

(8)    　先生で行った

(9)    　先生に行く

(10)               　先生に行った

以上(1)から(10)における「先生」を「自転車」，「学校」，「僕」で置き換えたもの，置き換えを行った結果得られるそれぞれの文に対して，「行ｋ」を「殴ｒ」，「見」で置き換えたものが生成され，合計120個の文が生成される．

以下，句構造規則(3)，(5)，(6)により無限個の文が生成される．

 

演習２　次の二つの構文木が得られる．

解析木１

この解析木１は，「僕」は「先生」と「僕」が共同で所有している「自転車」に乗って「学校」に「行った」ことを表している．

解析木２

この解析木２は，「僕」は「先生と僕の自転車」を使って「学校」に「行った」ことを表しており，意味的に正しい文であるためには「途中までは先生におぶわれて，その後は自転車に乗って学校に行った」というような，少し無理のある解釈が必要になる．

「と」を格助詞とする規則があると，曖昧さの数はさらに増える．

 

演習３　すべての書き換え規則はA→Xαと書くことができる．ここで，Aは非終端記号，Xは非終端記号または終端記号，αは0個以上の非終端記号と終端記号の列である．書き換え規則A→Xαがチョムスキーの標準形でないならば，次の手順でチョムスキーの標準形に変換することができる．

(1)   Xが非終端記号のとき．

新しい非終端記号Bを用意し，書き換え規則A→XαをA→XBとB→αで置き換える．

書き換え規則B→αに対して再び変換を適用する．

(2)   Xが終端記号のとき．

新しい終端記号BとCを用意し，書き換え規則A→XαをA→BCとB→X，C→αで置き換える．

書き換え規則C→αに対して再び変換を適用する．

 

図1.7の句構造規則の中でチョムスキーの標準形でないものは(5)と(6)である．書き換え規則(5)は次のようにしてチョムスキーの標準形に機械的に変換される．

(5)         NP → NPのNP

(5’)        NP → NP A

                            A → のNP

(5’’)        NP → NP A

                            A → B NP

                            B → の

同様に書き換え規則(6)は次の三つの規則に機械的に変換される．

              (6’’)        NP → NP C

                            C → D NP

                            D → と

しかし，ここで導入された非終端記号AとCは文法的な範疇に対応しているとは言えない．この場合には，次の(5’’’)と(6’’’)のような規則に変換した方が自然言語の文法としては望ましい．

(5’’’)       NP → ADN NP

                            ADN → NP NO

                            NO → の

              (6’’)        NP → ADN NP

                            ADN → NP TO

                            TO → と

 

演習４　チョムスキーの標準形からグライバッハの標準形への変換は，次の手順で簡単に行うことができる．

(1)   G=(VN,VT,P,S) をチョムスキー標準形の文法とし，VN={A1,A2,…,Am}とする．

(2)   書き換え規則Ai→Ajα ( j ＜ i)に対して，Ajを左辺にもつすべての書き換え規則Aj→βについて，Ai→βαを書き換え規則の集合に追加して，すべての書き換え規則Ai→Ajαについて i ≦ j に変換する．

(3)   A → Aαのように右辺の先頭が左辺に等しい書き換え規則については，新しい非終端記号Zを導入して次の置き換えを行う．

A → Aα1,           A → Aα2,           …,          A → Aαr　

をAが右辺の先頭にある書き換え規則とし，

A → β1,             A → β2,             …,          A → βs　

をAが左辺にある残りの規則とすると，これらの規則を新しい非終端記号Zを使った次の規則で置き換える．

A → βi,              A → βiZ            ( 1≦i≦s )

Z → αi,              Z → αiZ            ( 1≦i≦r )

(4) 以上の手順で作られた書き換え規則の右辺の先頭に非終端規則Aがあるときは，それを左辺にもつすべての規則A → αの右辺で置き換えた規則と置き換えていくことで，グライバッハの標準形が得られる．

 

演習３の解答で示した(5’’’)(6’’’)を採用すると図1.7の句構造規則は次に示すチョムスキーの標準形に変換される．

(1)   S → PP VP

(2)   PP → NP P

(3)   VP → PP VP

(4)   VP → V TENS

(5)   NP → ADN NP

(6)   NP → N

(7)   ADN → NP NO

(8)   ADN → NP TO

(9)   N → 先生|自転車|学校|僕

(10)   P → は|が|を|で|に

(11)   V → 行k|殴r|見

(12)   TENS → ru | ita

(13)   NO → の

(14)   TO → と

ここで VN={S, PP, VP, NP, ADN, N, P, V, TENS, NO, TO} であるが，非終端記号の大小関係を明らかにするために，次の置き換えを行う．

S = A1

PP = A2

VP = A3

NP = A4

ADN = A5

N = A6

P = A7

V = A8

TENS = A9

NO = A10

TO = A11

この置き換えを行うと文法は次のようになる．

(1) A1 → A2 A3

(2) A2 → A4 A7

(3) A3 → A2 A3

(4) A3 → A8 A9

(5) A4 → A5 A4

(6) A4 → A6

(7) A5 → A4 A10

(8) A5 → A4 A11

(9) A6 → 先生|自転車|学校|僕

(10) A7 → は|が|を|で|に

(11) A8 → 行k|殴r|見

(12) A9 → ru | ita

(13) A10 → の

(14) A11 → と

ここで，変換手順(2)の条件に該当する規則は，

       (3) A3 → A2 A3

       (7) A5 → A4 A10

       (8) A5 → A4 A11

である．(3) A3 → A2 A3　は　A2 を規則A2 → A4 A7　の右辺で置き換えて

               (3’) A3 → A4 A7A3

に変換する．(7) A5 → A4 A10 は　A4　を規則(5) A4 → A5 A4　と規則　(6) A4 → A6　の右辺で置き換えて

              (7’) A5 → A5 A4A10

                   (7’’) A5 → A6A10

に変換する．同様に，(8) A5 → A4 A11　も　A4　を規則(5) A4 → A5 A4　と規則　(6) A4 → A6　の右辺で置き換えて

              (8’) A5 → A5 A4A11

                   (8’’) A5 → A6A11

に変換する．ここまでの変換で，文法は次のようになる．

(1) A1 → A2 A3

(2) A2 → A4 A7

(3’) A3 → A4 A7A3

(4) A3 → A8 A9

(5) A4 → A5 A4

(6) A4 → A6

(7’) A5 → A5 A4A10

(7’’) A5 → A6A10

(8’) A5 → A5 A4A11

(8’’) A5 → A6A11

(9) A6 → 先生|自転車|学校|僕

(10) A7 → は|が|を|で|に

(11) A8 → 行k|殴r|見

(12) A9 → ru | ita

(13) A10 → の

(14) A11 → と

次に，変換手順(3)の条件に該当する規則は，

(7’) A5 → A5 A4A10

(8’) A5 → A5 A4A11

であるから，ここで新しい非終端記号Zを導入して規則(7’)，(7’’)，(8’)，(8’’)を次の規則で置き換える．

(7’’) A5 → A6A10

(7’’’) A5 → A6A10Z

(7’’’’) Z → A4A10

(7’’’’’) Z → A4A10Z

(8’’) A5 → A6A11

(8’’’) A5 → A6A11Z

(8’’’’) Z → A4A11

(8’’’’’) Z → A4A11Z

これまでの変換で文法は次のようになる．

(1) A1 → A2 A3

(2) A2 → A4 A7

(3’) A3 → A4 A7A3

(4) A3 → A8 A9

(5) A4 → A5 A4

(6) A4 → A6

(7’’) A5 → A6A10

(7’’’) A5 → A6A10Z

(7’’’’) Z → A4A10

(7’’’’’) Z → A4A10Z

(8’’) A5 → A6A11

(8’’’) A5 → A6A11Z

(8’’’’) Z → A4A11

(8’’’’’) Z → A4A11Z

(9) A6 → 先生|自転車|学校|僕

(10) A7 → は|が|を|で|に

(11) A8 → 行k|殴r|見

(12) A9 → ru | ita

(13) A10 → の

(14) A11 → と

以下，この集合に変換手順(4)を施してグライバッハの標準形が得られる．例えば，規則(1) A1 → A2 A3　は次のように変換される．

(1)   A1 → A2 A3

(1’) A1 → A4 A7A3                           A2を(2) A2 → A4 A7の右辺で置き換える

(1’’) A1 → A5 A4A7A3                       A4を(5) A4 → A5 A4の右辺で置き換える

A1 → A6A7A3                           A4を(6) A4 → A6の右辺で置き換える

(1’’’) A1 → A6A10 A4A7A3                 A5を(7’’) A5 → A6A10の右辺で置き換える

A1 → A6A10Z A4A7A3                A5を(7’’’) A5 → A6A10Zの右辺で置き換える

A1 → A6A11A4A7A3                    A5を(8’’) A5 → A6A11の右辺で置き換える

A1 → A6A11Z A4A7A3                A5を(8’’’) A5 → A6A11Zの右辺で置き換える

A1 → A6A7A3

(1’’’’) A1 → {先生|自転車|学校|僕}A7A3                     A6を(9)の右辺で置き換える

A1 → {先生|自転車|学校|僕}A10 A4A7A3             A6を(9)の右辺で置き換える

A1 → {先生|自転車|学校|僕}A10Z A4A7A3           A6を(9)の右辺で置き換える

A1 → {先生|自転車|学校|僕}A11A4A7A3                  A6を(9)の右辺で置き換える

A1 → {先生|自転車|学校|僕}A11Z A4A7A3              A6を(9)の右辺で置き換える

非終端記号を元の記号に書き換えると(1’’’’)は次のようになる．

(1’’’’) S → {先生|自転車|学校|僕} P VP

S → {先生|自転車|学校|僕} NO NP P VP

S → {先生|自転車|学校|僕} NO Z NP P VP

S → {先生|自転車|学校|僕} TO NP P VP

S → {先生|自転車|学校|僕} TO Z NP P VP

書き換え規則(2)から(8’’’’’)も同様の手順でグライバッハの標準形に変換する．

 

演習５　文脈自由文法で記述できて，正規文法で記述できない文に次のものがある．

              uviwxiy                ( i =1,2,… )

ここで，u，v，w，x，yは終端記号の列である．これは，長い文字列において十分離れたところにある２つの文字列の関係が文脈自由文法では規定できるが，正規文法では規定できないことを表している．

　一方，文脈自由文法では { anbncn | n = 1,2, …} という形の言語を生成する文法が記述できないことが分かっている．つまり，文脈自由文法では十分離れたところにある３つの文字列の関係は規定することができない．

演習６　最汎単一化作用素をみつける単一化アルゴリズムは次の文献に示されている．

 

Chin-Liang Chang, Richard Char-Tung Lee 著，

長尾真，辻井潤一訳，

コンピュータ・サイエンス研究書シリーズ27

「コンピュータによる定理の証明」，

日本コンピュータ協会(1983)，

pp.80．

 

Eugen Charniak, Drew MacDermott,

Artificial Intelligence,

Addison-Wesley Publishing Company(1985),

pp.348.

 

具体的なプログラムについては，Ｌｉｓｐで書かれたものが次の文献に示されている．

 

Gerald Gazdar, Chris Mellish,

Natural Language Processing in LISP,

Addison-Wesley Publishing Company(1989),

pp.235.

 

演習７　

(1) f(x), f(g(y))                   { g(y)/x }

(2) f(x), f(g(x))                   単一化不可能

(3) f(a,g(a)), f(x, x)            単一化不可能

(4) f(a, g(a)), f(x, y)           { a/x, g(a)/y }

 

演習８

 

 

 

 

 

 

 

 

 

 

 

 

 

演習９

(1)    猫は嫌いです                                                         猫：総称名詞

(2)    うちの猫はネズミを捕るのが得意です                  猫：定名詞、ネズミ：総称名詞

(3)    一匹の猫が飛び出して来ました                             猫：特定性不定名詞

(4)    塀の上には猫がいましたか                                    塀：定名詞、猫：不特定性不定名詞

 

演習１０　ここでは PATR で記述した簡単な英語の文法を示す。PATR について次の文献に解説がある。

 

(1)   Stuart M. Shieber : An Introduction to Unification-Based Approaches to Grammar, CSLI Lecture Notes Number 4, CSLI(1986).

(2)   Gerald Gazdar, Chris Mellish : Natural Language Processing in PROLOG,Addison-Wesley Publishing Company(1989).

 

S ---> NP VP :

              <S cat> = s,,

              <NP cat> = np,

              <VP cat> = vp,

              <S head>  =  <VP head>,

              <S sem> = <VP sem>,

<S sem arg0> = <NP sem>.

 

VP1---> VP2 PP :

              <VP1 cat> = vp,

              <VP2 cat> = vp,

              <PP cat> = pp,

              <VP1 sem> = <VP2 sem>,

              <VP1 sem mod> = <PP sem>.

 

VP ---> TV NP :

              <VP cat> = vp,

              <TV cat> = tv,

              <NP cat> = np,

              <VP head> = <TV head>,

<VP sem> = <TV sem>,

<VP sem arg1> = <NP sem>.

 

PP ---> P NP :

              <PP cat> = pp,

              <P cat> = p,

              <NP cat> = np,

<PP sem> = <P sem>,

<PP sem arg1> = <NP sem>.

 

NP ---> DET N :

              <NP cat> = np,

              <DET cat> = det,

              <N cat> = n,

              <NP head> = <N head>,

<NP sem> = <N sem>.

 

Word the :

              <cat> = det.

 

Word teacher :

              <cat> = n,

              <head agreement person> = third,

              <head agreement number> = singular,

<sem predicate> = teacher’.

 

Word school :

              <cat> = n,

              <head agreement person> = third,

              <head agreement number> = singular,

<sem predicate> = school’.

 

Word bicycle :

              <cat> = np,

              <head agreement person> = third,

              <head agreement number> = singular,

<sem predicate> = bicycle’.

 

Word ‘went to’ :

              <cat> = tv

<head tens> = past,

<sem predicate> = goto.

 

Word by :

              <cat> = p,

<sem predicate> = by.