形式文法による文章生成

「形式文法」について調べてみると、その厳密な定義やオートマトンと組み合わせた判定・解釈の話が多くて、具体的な文章生成に関する説明が見当たらない。
ここでは、形式文法によって文章を作り出す方法について、簡単な具体例を使って説明してみる。


■ はじめに


「形式文法による文章の生成」

文字の置き換えによる文章の生成」
のこと。



■ 例えば


<主語><述語>


という文字列があったときに、<主語>を「私は」に、<述語>を「寝る。」に置き換えると、


私は寝る。


という文章ができあがる。


■ だけど・・・

<主語>を「@%!」にして、<述語>を「★*」に置き換えると、


@%!★*


なにがなにやら・・・ということになってしまうので、置き換えに使える文字列は、予め決めておかなければならない。


最終的にできあがる文章は、次の単語しか使ってはいけないと決めておく。


{私は,あなたは,寝る。,食べる。}


つまり今回は、この4つの単語以外は最終的な文章に登場しない。


使ってよい言葉が決まった。
しかし、<主語>を「あなたは」にして、<述語>を「私は」に置き換えると、


あなたは私は


という文章ができあがる。これでは適切な文章とは言い難い。
そこで、文字の置き換えに次のようなルールを定める。


<主語>→「わたしは」または「あなたは」
<述語>→「寝る。」または「食べる。」


このような置き換えのルールを決めてあげることで、

<主語><述語>という文字列から、「わたしは寝る。」「わたしは食べる。」「あなたは寝る。」「あなたは食べる。」という4つの文章が作り出せる。


■ つまり・・

「使用できる言葉と、置き換えのルールを決めることで、適切な文章を作り出しましょう」


というのが形式文法の考え方。

使用できる単語や、置き換えルールを増やすことで、様々な変化に富んだ文章を作り出すことができる。


■ さて・・

少し天下り式になるけど、文章生成のときには、第一歩を踏み出すための初期状態が必要になる。
文章の作成は、あくまで「文字の置き換え」で実現するものだから、何もない空っぽの状態から、いきなり文章を作ることはできない。


そこで、まず最初の状態を


<文章>


で表すこととして、


<文章>→<主語><述語>


という新しい置き換えルールを追加する。


これによって、


<文章>→<主語><述語>→私は寝る。


という流れで文章が作られる。


■ まとめると

これまでに登場したものを全部まとめると、次のようになる。


□ 置き換えルールで、「置き換えられる側」のもの
{<文章>,<主語>,<述語>}

□ 使ってよい言葉
{私は,あなたは,寝る。,食べる。}

□ 置き換えルール
{
<文章>→<主語><述語>
<主語>→「わたしは」または「あなたは」
<述語>→「寝る。」または「食べる。」
}

□ 最初の状態
<文章>


■ 一般的な表現では

毎回、上のように書くのは大変だし、厳密ではないので、記号を使って次のように書く。
===============
N = {<文章>,<主語>,<述語>}
Σ = {私は,あなたは,寝る。,食べる。}
P = {
<文章>→<主語><述語>
<主語>→わたしは|あなたは
<述語>→寝る。|食べる。
}
S = <文章>
===============
これら全部をまとめて、1つの形式文法と呼ぶ。

つまり、形式文法の教科書に必ず出てくる

形式文法 G = {N,Σ,P,S}

だ。


■ 用語


N = {<文章>,<主語>,<述語>}
最後に出てくる文章には含まれないので非終端記号(non-terminal symbol)と呼ぶ。
必ず、何か別のものに置き換えられる必要がある。(もちろん決められたルールに従って)。


Σ = {私は,あなたは,寝る。,食べる。}
最後に出てくる文章に登場する。
これ以上、別のものに置き換えられることはないので、これを 終端記号(terminal symbol)と呼ぶ。


● 置き換えルールの集まりであるP生成規則(production rule)と呼ぶ。


● 初期状態を表すS開始記号(start symbol)と呼ぶ。



■ さらにもう一歩


これまでの例では、<文章>→<主語><述語>というルールによって、生成される文章は必ず、主語が1つ、述語が1つ含まれるものだった。
文章生成のルールに、次のようなものを追加したらどうなるだろう。


<文章>→<文章><文章>


1つの文章は、2つの文章から構成されることを許容する。というルールだ。


この場合、<文章>に対して、2つの置き換えルールが存在することになる。

<文章>→<主語><述語> (ルール1)
<文章>→<文章><文章> (ルール2)


適用できるルールが複数ある場合、どれか1つ、好きな方をランダムに選択すればよい。


つまり、



<文章>
↓ (ルール1を適用)
<主語><述語>

私は寝る。


でもいいし、



<文章>
↓ (ルール2を適用)
<文章><文章>
↓ (最初の<文章>にルール1を適用)
<主語><述語><文章>
↓ (最後の<文章>にルール1を適用)
私は食べる。<主語><述語>

私は食べる。あなたは寝る。

でも、構わないわけだ。


このようにして、新しいルールを1つ追加するだけで、長さが自在に変化する文章を作り出すことが可能になる。



■ 補足

今回説明した文法は「文脈自由文法(2型)」と呼ばれるもの。文脈(それまでの分の構造)に依存せずに、自由に次の置き換えをできるため。



■ 関連エントリ
論文自動生成プログラムSCIgen - 大人になってからの再学習


マッチ箱の脳(AI)―使える人工知能のお話

マッチ箱の脳(AI)―使える人工知能のお話


ブルックスの知能ロボット論―なぜMITのロボットは前進し続けるのか?

ブルックスの知能ロボット論―なぜMITのロボットは前進し続けるのか?