チョムスキー標準形で表すことのできる文法は全て文脈自由であり、また全ての文脈自由文法は、これと等価なチョムスキー標準形の文法に書換えることができるのはなぜですか?

できれば、いくつかの文脈自由文法を用いて説明してください。

http://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A7%E3%83%A0%E3%82%B9%E3%82%AD%E3%83%BC%E6%A8%99%E6%BA%96%E5%BD%A2

回答の条件
  • 1人2回まで
  • 登録:2009/02/04 16:15:08
  • 終了:2009/02/06 14:06:35

ベストアンサー

id:yo-kun No.1

yo-kun回答回数220ベストアンサー獲得回数302009/02/06 05:15:09

ポイント60pt

まず定義の確認です。


文脈自由文法とは、形式文法の置き換え規則が全て

A \to v

という形で表されるものです。

ただし、ここでAは1つの非終端記号であり、vは非終端記号と終端記号からなる長さ0以上の系列(文字列)です。

つまり、1つの非終端記号を別の何かに置き換える規則しかないものならばそれは文脈自由文法と呼びます。


一方チョムスキー標準形の定義は、形式文法の置き換え規則が

A \to BC

A \to \alpha

S \to \epsilon

の形からなるもののことです。

ただしA,B,Cは非終端記号で\alphaは終端記号、Sは開始記号、\epsilonは空系列です。

言い換えれば、形式文法の置き換え規則が

・1つの非終端記号を2つの非終端記号で置き換えるもの

・1つの非終端記号を1つの終端記号で置き換えるもの

・1つの開始記号を空系列に置き換えるもの

しかない場合、この形式文法をチョムスキーの標準形と呼びます。


つまりチョムスキー標準形の置き換え規則は全て1つの非終端記号を置き換えるものなので、文脈自由文法です。

(開始記号も非終端記号です)

よってご質問の前半である

「チョムスキー標準形で表される文法は全て文脈自由」

が言えるわけです。


さて、ご質問の後半部分である

「文脈自由文法はこれと等価なチョムスキー標準形の文法に書き換えることができる」

ことを示すにはやや長すぎるのでブログのほうに書きました。ご了承下さい。


以下、一般の文脈自由文法からチョムスキー標準系への変換の一例を書いておきます。


言語\left{ a^nb^n : n \ge 0 \right}を生成する文脈自由文法

 \left( \left{ S \right}, {a,b}, S, R \right)

をチョムスキーの標準形に変換する。

ただし、置き換え規則R

S \to aSb

S \to \epsilon


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

新しい開始記号S'を導入して文法を次のように変換する。

 \left( \left{ S',S \right}, {a,b}, S', R_1 \right)

ここで、置き換え規則R_1

S' \to S

S \to aSb

S \to \epsilon


(2) ε規則の除去

開始記号以外からのε規則S \to \epsilonがあるので、これを除去し文法を次のように変換する。

 \left( \left{ S',S \right}, {a,b}, S', R_2 \right)

ここで、置き換え規則R_2

S' \to S

S \to aSb

S \to ab


(3) 書き換え規則の除去

書き換え規則はないので除去の必要はない


(4) 長文規則の除去

長文規則S \to aSbがあるので、これを除去し文法を次のように変換する。

 \left( \left{ S',S,U_1,U_2 \right}, {a,b}, S', R_3 \right)

ここで、置き換え規則R_3

S' \to S

S \to aU_1

U_1 \to SU_2

U_2 \to b

S \to ab


(5) 最終処理

終端処理を含む2文字への置き換えS \to aU_1の代わりに

S \to U_3U_1

U_3 \to a

を導入し、終端処理2文字への置き換えS \to abの代わりに

S \to U_4U_5

U_4 \to a

U_5 \to b

を導入する。


以上によりチョムスキー標準形の形式文法

 \left( \left{ S',S,U_1,U_2,U_3,U_4,U_5 \right}, {a,b}, S', R_4 \right)

ここで、置き換え規則R_4

S' \to S

S \to U_3U_1

U_3 \to a

U_1 \to SU_2

U_2 \to b

S \to U_4U_5

U_4 \to a

U_5 \to b

を得る。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません