生成文法入門 II

前回の生成文法 I では、単語の並べ方に関して軽く見てみました。アリな単語の並び方にはどういう特徴があるのか、その線引き、記述をしようというのが生成文法のゴールです。

前回は「正規言語」に関してあまり深入りしなかったので、まずはそれを考えてみたいと思います。言語には使い物にならないのですが、そのせいか言語で例を示してもちょっとわからないので、チーズバーガーにします。

すごく単純なチーズバーガーを考えましょう。具材はバン、肉、チーズです。バンは上と下に1枚づつのみです。肉とチーズは増やせます。ただし、肉とチーズは増やせません。肉とチーズを同時に増やします。そうすると、以下のような組み合わせが可能です。

バン肉チーズバン　　　　　　　　　（いわゆるチーズバーガー）
バン肉チーズ肉チーズバン　　　　　（いわゆるダブルチーズバーガー）
バン肉チーズ肉チーズ肉チーズバン　（いわゆるトリプルチーズバーガー）
バン肉チーズ…肉チーズバン　　　　（いわゆらないNチーズバーガー）

これなら、遷移図、フローチャートみたいなやつをかけますね。まずは「バン」が1回、「肉 チーズ」 を好きなだけ繰り返して、最後に「バン」。

これは正規表現を使って正規言語として表記することができます。

バン ( 肉 チーズ )* バン

上に出てくる * は、その前の文字を繰り返すという記号です。この場合はカッコに対して * がかかっているので、カッコ内を（カッコ内の順番で）繰り返す、と言うことになります。（*は通常0回以上を示すので、今回の1回以上の場合は+を使うべきなんですが、ちょっとそれだと見にくいので、わざと*にしてます。）

これだと、バン肉チーズ…肉チーズバンは生成しても、バン肉チーズ肉バンとかバン肉チーズチーズとかは生成しません。

それだけのことです。

さて上の店では肉とチーズを交互に重ねますが、肉は肉だけ、チーズはチーズだけで同じ枚数だけ重ねる店があったとしましょう。

バン肉チーズバン　　　　　　　　　（チーズバーガー）
バン肉肉チーズチーズバン　　　　　（ダブルチーズバーガー）
バン肉肉肉チーズチーズチーズバン　（トリプルチーズバーガー）
バン肉…肉チーズ…チーズバン　　　　（Nチーズバーガー）

肉の枚数とチーズの枚数が同じである必要なければ、

バン 肉* チーズ* バン

で表記できます。

しかし、問題は肉とチーズが同数であるということ。これは正規表現では表記できないんです。もし表記できたら@zukashit 私までお知らせください。フローチャートも描けません。

文脈自由文法なら、バンが一回、肉を好きなだけ繰り返し、チーズを肉と同じ回数繰り返して、最後にバン、これができます。

S -> バン X バン
X -> 肉 X チーズ
X -> 肉 チーズ

Sから始めて、トリプルチーズバーガーを作ると、下のようになります。

一番下に、バン 肉 肉 肉 チーズ チーズ チーズ バン の順のものができました。

チーズばっかり重ねたトリプルチーズバーガーってちょっと嫌ですから、これはあまり実用的でないように感じますが、実は自然言語にはチーズを重ねるみたいな事が起こることが知られています。

ミサイル、怖いですね。英語で言うと missile ですね。そのためにミサイルを撃ち落とすためのミサイルが anti missile missile です。 せっかく打ったミサイルを撃ち落とされると迷惑なので、anti missile missile を撃ち落とすためのミサイルが anti anti missile missile missile です。じゃあ anti anti missile missile missile を撃ち落とすミサイルが anti anti anti missile missile missile missile です。

missile
anti missile missile
anti anti missile missile missile
anti anti anti missile missile missile missile
anti anti anti anti missile missile missile missile missile
anti anti anti anti anti missile missile missile missile missile missile

いずれどこかで疲れると思いますが、言語の上ではいくらでも続けられます。上であなたが バン 肉 肉 肉 チーズ チーズ チーズ バンのフローチャートを描こうとしてできなかったのと同様。anti anti anti missile missile missile missile （だけ）を生成するような正規表現というのは作れません。ムリなので是非やってみてください。

自然言語を記述するには文脈自由文法が必要なようです。実際には文脈依存文法が必要という話になってきたりします。

人間の脳にとか、言語習得がという話はしてません。自然言語を記述するという話です。習得されて、脳に詰まったものが自然言語なので関係なくはないんでしょうけど、まずは自然言語の記述を続けていきましょう。次からは英語の記述をちょっとやってみたいと思います。歴史的に英語の記述で始まったものなので、そこは避けないほうが良さそうです。