対象とする問題

ここでは、RNNを用いた、形式文法のうちの正規文法を対象とした文法推論の問題を扱う。
そこでまず簡単に、形式文法、正規文法、および文法推論についてそれぞれ説明し、その後対象とする文法について説明する。

• 形式文法
  文法Ｇは、｛Ｎ，Ｔ，Ｐ，Ｓ｝からなる。Ｎは非終端記号、Ｔは終端記号、Ｐはプロダクションルールの集合、Ｓは開始記号である。すべての文法には、生成または認識できる、終端記号の集合からなる言語Ｌが存在する。また同様に、その文法を生成または認識できるオートマトンが存在する。
  

• 正規文法
  句構造文法のチョムスキー階層において、もっとも単純な文法とそれに対応するオートマトンは、正規文法とFSAである。これがこの研究において対象とする文法のクラスである。
  

• 文法推論
  文法推論とは、未知の文法Ｇから導出される言語Ｌ（Ｇ）のうちの、有限長の文字列、またその補集合から、統語規則（またはプロダクションルール）を推論する手続きをおもに考える問題である。
  

• 対象とする文法
  RNNの文法推論能力を調べるため、ここではTomita(1982)によって作られ、また研究された、７つの比較的単純な文法を用いる。この形式文法は、それ自体が最も基本的表現からなるため、特徴抽出等の技術を必要としない。そのため、ここではこれを学習のテストに用いる。ここで示すのは、学習しやすい単純な正規文法である。それらはすべて0,1*からなる無限長のものを含む言語であり、3〜6状態のFSAで表される。
  これらの文法から生成される言語は次のように表される。
  

  ＃１ １*
  ＃２ （１０）*
  ＃３ 連続した奇数個の１のあとにはいつでも偶数個の０が続く
  ＃４ すべての文字列は"０００"を含まない
  ＃５ 偶数個の０と偶数個の１
  ＃６ （１の個数）−（０の個数）＝（３の倍数）
  ＃７ ０*１*０*１*
  

  ここで実験に用いられるのはこのうちの４番のものである。この文法に対応するFSAは空文字列を受理するものについては４つ、受理しないものについては5つの状態を持つ。