yo-kunの日記

■[はてな][計算機科学]文脈自由文法のチョムスキー標準形への変換

※本エントリは人力検索はてなの質問http://q.hatena.ne.jp/1233731707に対する回答の一部です

まずいくつかの用語を定義することにします。

• のような置き換え規則をε規則と呼ぶ(は非終端記号、は空系列)
• のような置き換え規則を読み換え規則と呼ぶ(は非終端記号)
• (uは長さが3以上の系列)のような規則を長文規則と呼ぶ

上に挙げた3つの置き換え規則は、文脈自由文法の置き換え規則としては許されるものですが、チョムスキー標準形には当てはまらないものです。

(ε規則は左辺の非終端記号が開始記号の場合だけはチョムスキーの標準形に当てはまります)

文脈自由文法の置き換え規則の中で上に挙げたものがある場合、その置き換え規則を除去して等価な置き換え規則を追加していけばチョムスキー標準形になるという理屈です。

(1) 新しい開始記号の導入

まず、文脈自由文法の開始記号を別の開始記号に置き換えます。

つまり、非終端記号に新たなを追加し、このを開始記号にして、なおかつ置き換え規則に

を追加します。

こうしてできた文法は開始記号が異なるだけなので元の文法と等価です。

これにより、文法の開始記号が置き換え規則の右辺に現れないことが保証されます。

(2) ε規則の除去

文法の置き換え規則の中に、ε規則

がある場合、Ａが開始記号でないならばＡが置き換え規則の右辺に現れる置き換え規則を適用可能な限り全て変更します。

例えば、置き換え規則

がある場合、この置き換え規則を除去し、代わりに

を置き換え規則に追加します。

このような処理を全て行った後、元のε規則を置き換え規則から除去します。

これは元の文法と等価です。

開始記号からのε規則以外の全てのε規則をこのように除去します。

(3) 読み換え規則の除去

文法の置き換え規則の中に、読み換え規則

がある場合、が置き換え規則の左辺に現れる置き換え規則を全てからの置き換えに変更します。

例えば、置き換え規則

がある場合、この置き換え規則を除去して

を置き換え規則に追加します。

このような処理を全て行った後、元の読み換え規則を置き換え規則から除去します。

これは元の文法と等価です。

全ての読み換え規則をこのように除去します。

(4) 長文規則の除去

文法の置き換え規則の中に、長文規則

がある場合、新たな非終端記号を導入して

...

を置き換え規則に追加し、元の長文規則を置き換え規則から除去します。

これは元の文法と等価です。

全ての長文規則をこのように除去します。

(5) 最終処理

ここまでの操作により、形式文法内の全ての置き換え規則の右辺の系列の長さは2以下になります。

なぜならば、右辺に長さ3以上の系列を持つ置き換え規則は(4)で除去されているからです。

右辺の系列の長さが0のものがあるとすれば、(2)の操作により開始記号からのε規則

だけであることが保証されています。

また、右辺の系列の長さが1のものがあるとすれば、(3)の操作により終端記号への置き換え

の形のものだけであることが保証されています。

最期に右辺の系列の長さが2のもの

があるとします。(は終端記号か非終端記号)

このが共に非終端記号であれば、それは

という形なのでチョムスキーの標準形の条件を満たします。

が非終端記号でが終端記号の場合には、新たな非終端記号を導入してこの規則を

と変更すればそれぞれチョムスキーの標準形の条件を満たします。

また、逆にが終端記号でが非終端記号の場合も同様です。

が共に終端記号であれば、新たな2つの非終端記号およびを導入してこの規則を

としてやればよいのです。

以上の変換によって文脈自由文法の全ての置き換え規則がチョムスキーの標準形を満たすものになることがわかります。

参考文献：計算理論とオートマトン言語理論―コンピュータの原理を明かす (Information & Computing)